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_map map;
        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;
    }
}