[Top Interview 150] 290. Word Pattern

Solution)

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        dic = {}
        s = s.split()

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

        for i in range(len(pattern)):
            if pattern[i] not in dic:
                dic[pattern[i]] = s[i]
            else:
                if dic[pattern[i]] != s[i]:
                    return False

        dicCount = Counter(dic.values())
        
        for counts in dicCount.values():
            if counts > 1:
                return False
        
        return True

 
Problem: LeetCode
 
Time Complexity: O(m+n)
Space Complexity: O(m+n)

Explanation)

We're only going to consider this problem where s has as many words as the length of pattern.
 
We'll map pattern's character to s's word in a dictionary. 
 
After counting the frequencies of the dictionary's values (matching words of s), we'll find whether there is a word that has a frequency more than 1. 
 
If all the conditions above are passed, then return True.

Initialization)

Since we're going to map pattern with s, we'll need an empty dicitionary.
 
Also, instead of having a string that contains words, I thought it would be a lot easier to work with a list of words. We can accomplish this by splitting s.
 

def wordPattern(self, pattern: str, s: str) -> bool:
        dic = {}
        s = s.split()

Compare lengths)

If the lengths of pattern and the list of s are different, it means s does not follow the pattern. Thus, we'll compare their lengths and focus on a case where pattern and the list of s have the same lengths.
 

def wordPattern(self, pattern: str, s: str) -> bool:
        dic = {}
        s = s.split()

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

Fill up the dictionary)

We'll match the character of pattern with the word of s.
 
If a new character is found, we'll add that character with the matching word to a dictionary.
If a character that already exists in a dictionary is found, we'll check if that character's word is the same as the current word. If they are not the same, False will be returned.
 

def wordPattern(self, pattern: str, s: str) -> bool:
        dic = {}
        s = s.split()

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

        for i in range(len(pattern)):
            if pattern[i] not in dic:
                dic[pattern[i]] = s[i]
            else:
                if dic[pattern[i]] != s[i]:
                    return False

Frequencies of dictionary's values)

After the cahracters of pattern and the words of s are matched, we'll check the frequencies of the words of s that are matched to the characters of pattern.
 
If the same word is matched to two or more different characters, it's not a bijection. Thus using Counter, we'll count the words' frequencies.
 
And if a certain word's frequency happens to be more than one, we'll return False. 
 
If all the conditions above are passed, we can return True.
 

def wordPattern(self, pattern: str, s: str) -> bool:
        dic = {}
        s = s.split()

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

        for i in range(len(pattern)):
            if pattern[i] not in dic:
                dic[pattern[i]] = s[i]
            else:
                if dic[pattern[i]] != s[i]:
                    return False

        dicCount = Counter(dic.values())
        
        for counts in dicCount.values():
            if counts > 1:
                return False
        
        return True

 
 
I tried my best to use less memory and run faster, but this was the best that I could come up with. If there is a better code you wrote, let me know!