Solution For Word Pattern
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.
Step by Step Implementation For Word Pattern
public class Solution { public boolean wordPattern(String pattern, String str) { String[] words = str.split(" "); if (words.length != pattern.length()) return false; Map index = new HashMap(); for (int i=0; i def wordPattern(pattern, str): s = pattern t = str.split() return map(s.find, s) == map(t.index, t)var wordPattern = function(pattern, str) { var words = str.split(" "); if (words.length !== pattern.length) return false; var map = {}; for (var i = 0; i < words.length; i++) { if (!map[pattern[i]]) { if (Object.values(map).includes(words[i])) return false; map[pattern[i]] = words[i]; } else if (map[pattern[i]] !== words[i]) { return false; } } return true; };class Solution { public: bool wordPattern(string pattern, string str) { unordered_mapmap; istringstream in(str); int i = 0, n = pattern.size(); for (string word; in >> word; ++i) { if (i == n || map.count(pattern[i]) && map[pattern[i]] != word || !map.count(pattern[i]) && map.count(word)) return false; map[pattern[i]] = word; } return i == n; } }; public class Solution { public bool WordPattern(string pattern, string str) { // create a map for character to word var map = new Dictionary(); // create a set to keep track of mapped words var set = new HashSet (); // split input string into an array of words var words = str.Split(' '); // if the number of words does not match the number of characters in the pattern, return false if (words.Length != pattern.Length) { return false; } // loop through each character in the pattern for (int i = 0; i < pattern.Length; i++) { var c = pattern[i]; var w = words[i]; // if the character is not in the map, add it if (!map.ContainsKey(c)) { map.Add(c, w); } // if the mapped word for the character does not match the current word, return false if (map[c] != w) { return false; } // if the set of mapped words already contains the current word, return false if (set.Contains(w)) { return false; } // add the current word to the set of mapped words set.Add(w); } // if we've gotten this far, the pattern and string match return true; } }