LeetCode #290 Word Pattern Solution & Explanation

Klook.com
Post Views: 315

LeetCode Problem

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.

Solution

This looks like we can solve it with an iteration with dictionary.

C# Solution

❌First Try

public class Solution {
    public bool WordPattern(string pattern, string s) {
        Dictionary<char,string> dict =   new Dictionary<char,string>();
        string[]res = s.Split(" ");

        for(int i = 0; i< pattern.Length;i++)
        {
            var p = pattern[i];
            if (!dict.ContainsKey(p))
            {
                dict.Add(p, res[i]);
            }
            else    //check if exists
            {
                if(res[i] != dict[p])
                {
                    return false;
                }
            }
        }

        return true;

    }
}

Failed while pattern = “abba” , s = “dog dog dog dog”

We need to check if each character corresponds to a distinct word.

❌Second Try – still failed, didn’t check if the Length equals

public class Solution {
    public bool WordPattern(string pattern, string s) {
        Dictionary<char,string> dict =   new Dictionary<char,string>();
        HashSet<string> hSet = new HashSet<string>();
        string[]res = s.Split(" ");

        for(int i = 0; i< pattern.Length;i++)
        {
            var p = pattern[i];
            var r = res[i];
            if (!dict.ContainsKey(p))
            {
                if(hSet.Contains(r))
                {
                    return false;
                }
                dict.Add(p, r);
                hSet.Add(r);
            }
            else    //check if exists
            {
                if(res[i] != dict[p])
                {
                    return false;
                }
            }
        }

        return true;

    }
}

Failed while pattern = “aaa” , s = “aa aa aa aa”

Solution1 – Dictionary & HashSet

public class Solution {
    public bool WordPattern(string pattern, string s) {
        Dictionary<char,string> dict =   new Dictionary<char,string>();
        HashSet<string> hSet = new HashSet<string>();
        string[]res = s.Split(" ");

        if(res.Length != pattern.Length)
        {
            return false;
        }

        for(int i = 0; i< pattern.Length;i++)
        {
            var p = pattern[i];
            var r = res[i];
            if (!dict.ContainsKey(p))
            {
                if(hSet.Contains(r))
                {
                    return false;
                }
                dict.Add(p, r);
                hSet.Add(r);
            }
            else    //check if exists
            {
                if(r != dict[p])
                {
                    return false;
                }
            }
        }

        return true;
    }
}

Java Solution

Solution1

class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<Character, String> dict = new HashMap<Character, String>();
        HashSet<String> hSet  = new HashSet<String>();

        String[]res = s.split(" ");

        if(res.length != pattern.length())
        {
            return false;
        }

        for(int i = 0; i< pattern.length();i++)
        {
            char p = pattern.charAt(i);
            String r = res[i];
            if (!dict.containsKey(p))
            {
                if(hSet.contains(r))
                {
                    return false;
                }
                dict.put(p, r);
                hSet.add(r);
            }
            else    //check if exists
            {
                if(!r.equals(dict.get(p)))
                {
                    return false;
                }
            }
        }

        return true;
    }
}

Runtime : 1ms、1ms、1ms

Python3 Solution

Solution1

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        dict = {}
        hSet = set()
        res = s.split(" ")

        if(len(res) != len(pattern)):
            return False

        for i in range (len(pattern)):
            p = pattern[i]
            r = res[i]
            if (p not in dict):
                if(r in hSet):
                    return False
                
                dict[p] = r
                hSet.add(r)
            
            else:    #check if exists
                if(r != dict[p]):
                    return False

        return True

JavaScript Solution

Solution1

/**
 * @param {string} pattern
 * @param {string} s
 * @return {boolean}
 */
var wordPattern = function(pattern, s) {
    const dict = new Map();
    const hSet = new Set();

    const res = s.split(" ");

    if (res.length !== pattern.length) 
    {
        return false;
    }

    for (let i = 0; i < pattern.length; i++) 
    {
        const p = pattern.charAt(i);
        const r = res[i];
        if (!dict.has(p)) 
        {
            if (hSet.has(r)) 
            {
                return false;
            }
            dict.set(p, r);
            hSet.add(r);
        } 
        else // check if exists
        { 
            if (r !== dict.get(p)) 
            {
                return false;
            }
        }
    }

    return true;

};

Conclusion

I thought this problem was easy, considering that we’ve encountered a similar issue before!

You can find our previous approach here at LeetCode#387 – First Unique Character in a String.

We utilized both a dictionary and a hashMap to address the problem of string existence.

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Word Pattern – LeetCode

Some Random post

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *