290. Word Pattern

 

Word Pattern

Problem Description

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 lowercase 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.

Given a template and a string, determine whether the string follows the format of the template.

The compliance here is to say that each word in the string has a consistent correspondence with the template.

Example:
pattern = "abba", str = "dog cat cat dog" should return true. pattern = "abba", str = "dog cat cat fish" should return false. pattern = "aaaa", str = "dog cat cat dog" should return false. pattern = "abba", str = "dog dog dog dog" should return false.

It can be assumed that there are only lowercase letters in the template and that each word in the string is separated by whitespace.

idea:

1. This is more than 95% similar to 205. Isomorphic Strings
2. Similarly, the map is used to store the correspondence between the pattern and the string that has appeared. When it is found that the correspondence is not established, it will return false.

Let`s Code It!

/**
 * @param {string} pattern
 * @param {string} str
 * @return {boolean}
 */
var wordPattern = function(pattern, str) {
    var patternMap = {};
    var strMap = {};
    var ary = str.split(/\s/)

    // The length of the template and the number of words in the string are sorry false
    if(pattern.length != str.split(/\s/).length){
        return false;
    }

    for(var i in pattern){
        var p = pattern[i];
        var s = ary[i];
        // The pairing that has not appeared is added to the map, and the pairing that has appeared is compared
        if(!patternMap[p]){
            patternMap[p] = s;
        } else if(patternMap[p] != s){
            return false;
        }

        if(!strMap[s]){
            strMap[s] = p;
        }  else if(strMap[s] != p) {
            return false;
        }

    }

    return true;
};

OR

/**
 * @param {string} pattern
 * @param {string} s
 * @return {boolean}
 */
var wordPattern = function(pattern, s) {
    let words = s.split(" ");
    if(words.length != pattern.length){
        return false;
    }
    let hashmap = {};
    let set = [];
    for(let i=0;i<pattern.length;i++){
        if(hashmap[pattern[i]]){
            if(hashmap[pattern[i]] != words[i]){
                return false;
            }
        }else{
            if(set.includes(words[i])){
                return false
            }
            set.push(words[i]);
            hashmap[pattern[i]] = words[i];
        }
    }
    return true;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #290. Word Pattern

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!