290. Word Pattern LeetCode Solution

In this guide, you will get 290. Word Pattern LeetCode Solution with the best time and space complexity. The solution to Word Pattern problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Word Pattern solution in C++
Word Pattern solution in Java
Word Pattern solution in Python
Additional Resources

290. Word Pattern LeetCode Solution image

Problem Statement of 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. Specifically:

Each letter in pattern maps to exactly one unique word in s.
Each unique word in s maps to exactly one letter in pattern.
No two letters map to the same word, and no two words map to the same letter.

Example 1:

Input: pattern = “abba”, s = “dog cat cat dog”
Output: true
Explanation:
The bijection can be established as:

‘a’ maps to “dog”.
‘b’ maps to “cat”.

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

290. Word Pattern LeetCode Solution in 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-bounds
        return false;
      if (charToIndex[pattern[i]] != stringToIndex[word])
        return false;
      charToIndex[pattern[i]] = i + 1;
      stringToIndex[word] = i + 1;
    }

    return i == n;
  }
};
/* code provided by PROGIEZ */

290. Word Pattern LeetCode Solution in 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;
  }
}
// code provided by PROGIEZ

290. Word Pattern LeetCode Solution in Python

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