[LeetCode] 290. Word Pattern

출처 : https://leetcode.com/problems/word-pattern/

Word Pattern - LeetCode

 

1. 문제 설명

문자열 pattern과 문자열 s가 주어진다. 주어진 패턴을 따르는 문자열 s를 찾는 문제이다.

ex)

pattern = "abba"    s = "dog cat cat dog" (True)

                              s = "cat cat dog dog" (False)

 

 

 

 

2. 접근 방식

1. 문자열 s를 공백 기준으로 분리시켜 list로 만든다.

2. 패턴의 문자열 길이와 s의 문자열 길이가 다르거나 중복을 제거한 패턴의 문자열 길이와 중복을 제거한 s의 문자열 길이가 다르면 return False

3. for 반복문을 돌면서 딕셔너리 안에 해당 패턴이 존재하지 않으면 dic['패턴'] = s['문자']를 삽입하고 

딕셔너리에 해당 패턴이 존재하고 그 패턴의 값과 s['문자']가 일치하지 않으면 return False

4. 반복문을 빠져나오게 되면 모두 일치하므로 return True

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

from collections import defaultdict
class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        s = list(s.split()) # 문자열 s를 list형태로 바꾼다.
        dic=defaultdict(str) # key값이 str형태인 딕셔너리를 만든다. 
        if len(pattern) != len(s) : # 중복을 제거하지 않은 상태의 각 문자의 길이가 다르다면 
            return False # False
        if len(set(pattern)) != len(set(s)) : # 중복을 제거한 후의 각 문자의 길이가 다르다면 
            return False # False
        for i in range(len(pattern)) : 
            if pattern[i] in dic and s[i] != dic[pattern[i]] : # dic 내부에 존재하고 패턴일치하지 않는다면 
                return False # False
            elif pattern[i] not in dic : # dic안에 존재하지 않는다면 
                dic[pattern[i]] += s[i] # 추가 
            
        return True # 패턴이 모두 일치하여 반복문을 빠져 나왔으면 True

 

4. 분석

Time : O(n) - for 반복문을 돌면서 hash map 삽입

Space : O(n)
소요시간 : 15분 
제출 횟수 (무작정 제출하기 않기)  : 2회 
어려웠던 부분과 해결한 방법 : 중복을 제거한 문자의 길이를 놓침 -> 고민 후 해결
실수가 줄어들었는가 ? 

- 문제를 꼼꼼히 읽는 습관 가지기