[Leetcode] 290. Word Pattern

📄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 lower-case 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.

💻 My Submission

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        if len(set(pattern))!=len(set(s.split())):
            return False
        _dict=defaultdict(str)
        for s1, s2 in zip(pattern, s.split()):
            _dict[s1]=s2
        
        if [_dict[x] for x in pattern]==s.split():
            return True
        return False

🎈 Better Solution

    words, w_to_p = s.split(' '), dict()

    if len(p) != len(words): return False
    if len(set(p)) != len(set(words)): return False # for the case w = ['dog', 'cat'] and p = 'aa'

    for i in range(len(words)):
        if words[i] not in w_to_p: 
            w_to_p[words[i]] = p[i]
        elif w_to_p[words[i]] != p[i]: 
            return False

    return True

References

• https://leetcode.com/problems/word-pattern/
• https://leetcode.com/problems/word-pattern/discuss/1695840/Python3-SINGLE-HASHMAP-(**)-Explained