풀이_LC290.md

😑 LeetCode 290. Word Pattern

• Date : 2021.08.29(일)
• Time : 30분

Problem

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

Constraints

• 1 <= pattern.length <= 300
• pattern contains only lower-case English letters.
• 1 <= s.length <= 3000
• s contains only lower-case English letters and spaces ' '.
• s does not contain any leading or trailing spaces.
• All the words in s are separated by a single space.

Example

• Input: pattern = "abba", s = "dog cat cat fish"
• Output: false

풀이

    def wordPattern(self, pattern: str, s: str) -> bool:
        word = s.split()

        if len(pattern) != len(word): return False
        dic = {}

        for i in range(0,len(pattern),1):
            if (pattern[i] not in dic.keys()):
                if word[i] in dic.values(): return False
                else : dic[pattern[i]] = word[i]
            elif not dic[pattern[i]] == word[i]:
                return False
            
        return True
        

: 이 문제는 문장 s가 pattern의 형태를 띄고 있는지 검사하는 문제이다. abba -> "min hee hee min" 으로 a: min, b: hee 패턴으로 적용되는 것이다. 그렇기 때문에 딕셔너리로 문제를 해결했다. 먼저 문장을 스페이스 기준으로 잘라준다. patten의 길이와 문장의 길이가 다르다면 패턴을 적용하지 못하므로 바로 False 값을 준다. 이제 for 문으로 pattern의 갯수만큼 돌아주면도니다. 이 때 딕셔너리에 key 값이 패턴이 있는지 검사한다. 만약 이미 있는 패턴이라면 value값이 동일하지 검사한다. 하지만 아직 없는 패턴이라면 New패턴으로 등록해줘야한다. 근데 여기서 생각도 못한 예외가 있었다! 만약 a 패턴에 이미 "min"이라는 것이 등록되어 있다면, b패턴에는 얘기 등록될 수 없다. a패턴의 value로 들어갔기 때문이다. 다른 패턴끼리 value가 같을 수 없다.. 그렇기 때문에 if word[i] in dic.values()을 검사해줘야하는게 포인트!