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. Specifically:

• Each letter in pattern maps to exactly one unique word in s.
• Each unique word in s maps to exactly one letter in pattern.
• No two letters map to the same word, and no two words map to the same letter.

Example 1:

• Input: pattern = “abba”, s = “dog cat cat dog”
• Output: true
• Explanation:
  The bijection can be established as:
  • ‘a’ maps to “dog”.
  • ‘b’ maps to “cat”.

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.

Submitted Code

class Solution(object):
    def wordPattern(self, pattern, s):
        """
        :type pattern: str
        :type s: str
        :rtype: bool
        """
        hash = {}
        words = s.split()
        
        if len(pattern) != len(words):
            return False
        
        for i in range(len(pattern)):
            if pattern[i] not in hash and words[i] not in hash.values():
                hash[pattern[i]] = words[i]
            elif pattern[i] not in hash and words[i] in hash.values():
                return False
            elif pattern[i] in hash and hash[pattern[i]] != words[i]:
                return False
        return True

Runtime: 0 ms | Beats 100.00%
Memory: 12.52 MB | Beats 12.59%

Other Solutions

1st

from itertools import zip_longest

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:

        s = s.split()

        return (len(set(pattern)) ==
                len(set(s)) ==
                len(set(zip_longest(pattern,s))))

time complexity: 𝑂(𝑛)
space complexity: 𝑂(𝑛)

pattern의 고유한 문자 개수 == s의 고유한 단어 개수 == pattern과 s를 짝지은 (문자, 단어) 쌍의 고유한 개수
zip_longest는 두 길이가 다를 경우 누락된 값에 None을 넣어서 길이를 맞추기 때문에 사용한 것 같다.

2nd

class Solution(object):
    def wordPattern(self, pattern, s):
        words = s.split()
        if len(pattern) != len(words):
            return False
        
        char_to_word = {}
        word_to_char = {}
        
        for c, w in zip(pattern, words):
            if c in char_to_word:
                if char_to_word[c] != w:
                    return False
            else:
                char_to_word[c] = w
            
            if w in word_to_char:
                if word_to_char[w] != c:
                    return False
            else:
                word_to_char[w] = c
        
        return True