Leetcode Problem 290 Word Pattern.txt

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.




Hint: Use dict to traverse if same key is present then return false otherwise record the word for the pattern character.
Edge case: If word itself is already recorded then check for that case as well by recording in another dict.


Solution

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split(' ')
        wordDict = {}
        uniqueWords = {}
        if(len(words) != len(pattern)):
            return False
        for i in range(len(words)):
            currentWord = words[i]
            currentPattern = pattern[i]
            if(currentPattern in wordDict):
                if wordDict[currentPattern] == currentWord:
                    continue
                else:
                    return False
            else:
                if currentWord in uniqueWords:
                    return False
                wordDict[currentPattern] = currentWord
                uniqueWords[currentWord] = currentPattern
        return True