[LeetCode] 290. Word Pattern

 Easy 문제로 설명과 예시는 아래와 같다.

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

 

 Pattern과 String이 주어지고 주어진 String은 공백(space)를 통해 단어를 구분해뒀고, 각 단어를 하나의 문자로 치환했을 때 주어진 pattern과 일치가 가능하다면 true 그렇지 않으면 false를 반환하면 된다. Easy 문제임에도 acceptance rate는 41.7% 밖에 되지 않는다. Dictionary(Hash map)을 이용해 풀었다. 주어진 Pattern의 길이와 주어진 단어의 개수가 다르면 우선 일치할 수 없기에 그 부분을 확인해 다르면 false를 반환해주었고, Dictionary의 key로 pattern의 각 element를 String의 각 단어를 value로 활용해 한 번 확인했고, key를 통해 한 번 더 확인했다. 처음엔 pattern의 element만을 key로 제출하니 모든 test case를 충족시킬 수 없없고 반대의 경우도 확인을 해줘야한다.

 

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

 아래는 Python으로 내가 작성한 솔루션이다. 

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = []
        i = 0
        while i < len(s):
            l = i
            bomb = 0
            while i < len(s) and s[i] != ' ':
                i += 1
            r = i
            words.append(s[l:r])
            i += 1

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

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

        return True