Word Pattern LeetCode Solution | Easy Approach

Word Pattern Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

Constraints:

• 1 <= pattern.length <= 300
• pattern contains only lower-case English letters.
• 1 <= s.length <= 3000
• s contains only lowercase English letters and spaces ' '.
• s does not contain any leading or trailing spaces.
• All the words in s are separated by a single space.

Word Pattern Solutions

✅Time: O(n)
✅Space: O(n)

C++

class Solution {
 public:
  bool wordPattern(string pattern, string str) {
    const int n = pattern.length();
    istringstream iss(str);
    vector<int> charToIndex(128);
    unordered_map<string, int> stringToIndex;

    int i = 0;
    for (string word; iss >> word; ++i) {
      if (i == n)  // out of bound
        return false;
      if (charToIndex[pattern[i]] != stringToIndex[word])
        return false;
      charToIndex[pattern[i]] = i + 1;
      stringToIndex[word] = i + 1;
    }

    return i == n;
  }
};

Java

 class Solution {
  public boolean wordPattern(String pattern, String str) {
    String[] words = str.split(" ");
    if (words.length != pattern.length())
      return false;

    Map<Character, Integer> charToIndex = new HashMap<>();
    Map<String, Integer> stringToIndex = new HashMap<>();

    for (Integer i = 0; i < pattern.length(); ++i)
      if (charToIndex.put(pattern.charAt(i), i) != stringToIndex.put(words[i], i))
        return false;

    return true;
  }
}

Python

class Solution:
  def wordPattern(self, pattern: str, str: str) -> bool:
    t = str.split()
    return [*map(pattern.index, pattern)] == [*map(t.index, t)]

Watch Tutorial

Checkout more Solutions here