LeetCode 290(Word Pattern, Python)

1. 문제 링크

• https://leetcode.com/problems/word-pattern/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

2. 문제 설명

• pattern과 문자열 s가 주어졌을 때, s가 같은 pattern을 따르는지를 True or False로 반환
  • 여기서 같은 패턴이다의 의미는, 
  • pattern과 s가 "bijection" 관계임을 의미 (bijection: 두 집합 사이를 중복 없이 일대일로 대응시키는 함수)
• 예제를 보면 좀 더 명확하다.
  • 예제1) pattern = "abba", s = "dog cat cat dog"라고 하면
    • a는 dog에, b는 cat에 1대1로 대응이 되기 때문에 True를 반환할 수 있다. 
  • 예제2) pattern = "abba", s = "dog cat cat fish"라고 하면,
    • a가 dog에만 대응되는 것이 아니라, dog 와 fish 두개에 대응이 되어, 일대일 대응이 되지 않는다.
    • 이에 Fasle를 반환한다. 
  • 예제3) pattern = "aaaa", s = "dog cat cat dog" 도 예제2와 마찬가지로,
    • a가 dog에만 대응이 되는 것이 아니라, dog, cat 두개의 단어에 대응이 되므로 False를 반환한다. 

 

3. 처음 풀이

• pattern과 s가 일대일 대응이 된다는 것은, 두개를 list로 변환하여 (2) zip을 중복 제외 시켰을 때 나오는 값의 개수가, 
  • (2) pattern의 중복제외 문자 수, (3) s의 중복제외 단어수와 동일하다고 할 수 있다. 
• 이에, 우선 pattern의 문자 개수와 s의 단어 개수가 다르면 False를 반환해두고,
• 그 이외의 케이스에 대해서는, (1) == (2) == (3)인지를 반환하는 것으로 코드를 작성하였다.
• runtime 90%로 통과

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        s=s.split(' ')
        if len(pattern) != len(s):
            return False

        return len(set(zip(list(pattern),s))) == len(set(list(pattern))) == len(set(s))

 

4. 다른 풀이 

• submission에 있는 많은 다른 풀이들은, hash table을 이용하여 풀었다.
• len(pattern)과 len(s.split())이 다르면 False를 하는 base code는 추가해두고, 
• char_to_word, word_to_char 라는 각 dict을 만들어둔 뒤에,
  • char가 char_to_word의 key로 존재하는데, 그에 해당하는 value가 word와 다르거나,
  • 반대로 word가 word_to_char의 key로 존재하는데, 그에 해당하는 valuerk char와 다르다면 False를 반환하고, 
  • 그이외의 경우에 대해서는 char,word / word,char에 대한 hash table을 구성하는 구조로 작성되어있다.
• 아마도 위의 내 풀이보다는, 아래 풀이가 더 정석적인 풀이가 아닐까 싶다.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(pattern) != len(words):
            return False
            
        char_to_word = {}
        word_to_char = {}
        
        for char, word in zip(pattern, words):
            if (char in char_to_word and char_to_word[char] != word) or \
               (word in word_to_char and word_to_char[word] != char):
                return False
                
            char_to_word[char] = word
            word_to_char[word] = char
            
        return True