290. Word Pattern

문제)

290. Word Pattern

 

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.

 

 

솔루션1)

- 패턴->단어 해시, 단어->해시 테이블을 유지

 

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        # 길이가 다르면 무조건 패턴 매칭 False
        if len(pattern) != len(s.split()):
            return False
        
        # 패턴과 단어 매칭 hash
        # a -> dog
        p_to_word = {}
        
        # 단어와 패턴 매칭 hash
        # dog -> a
        word_to_p = {}
        
        for p, word in zip(pattern, s.split()):
            if p not in p_to_word :
                if word not in word_to_p:                    
                    p_to_word[p] = word
                    word_to_p[word] = p
                else:
                    """
                    p_to_word:       dog_to_p:
                      a->dog          dog->a
                      b->dog          dog->b (->dog가 이미 a에 매칭되어 있으므로 에러)
                    """
                    return False                    
            else:
                if p_to_word[p] != word:
                    return False    
        return True

솔루션2)

- 솔루션1 코드 리팩토링

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        if len(pattern) != len(s.split()):
            return False        
        
        p_to_word = {}
        word_to_p = {}
        for p, word in zip(pattern, s.split()):
            if p in p_to_word and p_to_word[p] != word:
                return False
            if word in word_to_p and word_to_p[word] != p:
                return False
            p_to_word[p] = word
            word_to_p[word] = p
        return True

---

 

유사 문제, 205. Isomorphic Strings 문제 또한 동일한 접근법으로 문제 풀이 가능

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        c1_to_c2 = {}
        c2_to_c1 = {}
        
        for c1, c2 in zip(s, t):
            if c1 in c1_to_c2 and c1_to_c2[c1] != c2:                
                return False
            if c2 in c2_to_c1 and c2_to_c1[c2] != c1:                
                return False
            c1_to_c2[c1] = c2
            c2_to_c1[c2] = c1            
        
        return True