Python O(n) solution, only simple logic with dicts


  • 0
    S

    We can use two dicts: one that maps pattern characters to their corresponding word in str, and another that maps the reverse: words in str to their corresponding character in pattern. If these are 1-to-1 then it is correct.

    class Solution(object):
        def wordPattern(self, pattern, str):
            """
            :type pattern: str
            :type str: str
            :rtype: bool
            """
            pattern_to_str = {}
            str_to_pattern = {}
            strlist = str.split(' ')  # break str up into "words" by splitting by space character.
            
           # if the lengths of pattern and strlist are not equal, there isn't a 1-to-1 mapping, so it must be False/
            if len(strlist) != len(pattern):
                return False
            
            # We loop through each word in the pattern, checking if the pattern matches the string as we go.
            for i in range(len(pattern)):
                # if the current letter in the pattern was previously already mapped to a word in strlist. Thus it can't be a 1-to-1 relation.
                if pattern[i] in pattern_to_str:
                    if pattern_to_str[pattern[i]] != strlist[i]:
                        return False
                else:
                    # if the current letter in the pattern was not found, we make sure that that the word wasn't already assigned a pattern character. If wasn't then the word-letter combination is a new, so we add it to both dicts.  
                    if strlist[i] in str_to_pattern:
                        if str_to_pattern[strlist[i]] !=  pattern[i]:
                            return False
                    else:
                        pattern_to_str[pattern[i]] = strlist[i]
                        str_to_pattern[strlist[i]] = pattern[i]
            return True
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.