Word Pattern - Leetcode Solution

Problem Statement:

Given a pattern and a string str, return true if str follows the same pattern.

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

Constraints:

• You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.
• You may assume str contains at least one word.
• Time complexity: O(n)
• Space complexity: O(n)

Example 1:

• Input: pattern = "abba", str = "dog cat cat dog"
• Output: true

Example 2:

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

Example 3:

• Input: pattern = "aaaa", str = "dog cat cat dog"
• Output: false

Example 4:

• Input: pattern = "abba", str = "dog dog dog dog"
• Output: false

Solution:

We can solve this problem by creating a hash map that maps each character in the pattern to each word in the string str. We can use a set to ensure that the words are unique.

First, we split the string into words using the split() method and store the words in a string array called words. We initialize an empty dictionary called char_map to store the mapping between the characters in the pattern and the words in the string.

Next, we iterate over each character in the pattern and get its corresponding word in the words array. If the character is not already in the dictionary, we add it to the dictionary with its corresponding word as the value. If the character is already in the dictionary, we check if the corresponding word is the same as the current word. If not, we return false, as there is a mismatch between the pattern and the string.

At the end, we check if the length of the dictionary is the same as the length of the set of words. If not, it means there are duplicate values in the dictionary, which is not allowed according to the problem statement, so we return false.

If we make it to the end of the function without returning false, then we have successfully matched the pattern to the string, and we can return true.

Here is the Python code:

def wordPattern(pattern: str, str: str) -> bool: words = str.split() if len(pattern) != len(words): return False char_map = {} for i in range(len(pattern)): char = pattern[i] word = words[i] if char not in char_map: if word in char_map.values(): return False char_map[char] = word else: if char_map[char] != word: return False return len(char_map) == len(set(words))

Time Complexity: O(n), where n is the length of the string str.

Space Complexity: O(n), where n is the length of the string str.

1