[LeetCode] 290. Word Pattern

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.

 

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.

---

문제 풀이

• pattern과 s문자열이 주어진다. 
• 패턴은 알파벳이며 s문자열은 빈공간을 포함한다. 
• 제한 사항을 보면 문자열들의 길이는 작기 때문에 어떻게 풀어도 상관없다. 
• 하지만 패턴과 s문자열에 들어있는 단어를 매칭시켜야한다. 
• 이때 데이터들을 쌍으로 매칭하기 위해서는 해쉬 테이블을 사용할 수 있다. 
• 해쉬 테이블은 키와 벨류로 데이터를 묶어 저장할 수 있기 때문이다. 
• 각각 패턴에 맞는 단어들을 저장하기위해 패턴 딕셔너리를 선언한다.
• 그리고 s문자열은 어떠한 글자도 나올 수 있기 때문에 문자열 딕셔너리도 따로 선언해줘야한다. 
• 만일 패턴이 'aaa'이고 s문자열이 'a a a' 이런 테스트 케이스가 주어진다면 어떤것이 패턴인지 모를 수 있기 때문에 해쉬 테이블을 두개 사용한다. 
• s는 띄어쓰기 별로 단어들을 쪼개야해서 split함수를 쓴다. 
• 함수내에 아무것도 적지 않으면 띄어쓰기로 분리된다.
• 즉, pattern과 s문자열의 데이터를 각각 키와 벨류로 짝을 만들어 딕셔너리에 저장한다.
• for문으로 하나씩 탐색하면서 각각의 데이터들을 묶어 저장한다.
• 처음 단어와 패턴이 만날때 저장된것을 그 단어에 패턴이라고 생각하면 다음에 나오는 단어와 패턴이 이미 저장된 키, 벨류와 다르다면 오답니다. 
• 탐색 시작과 동시에 패턴을 고정하며 하나씩 틀린게 있는지 찾아나가는 것이다. 

소스 코드

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        hash_table_p = dict()
        hash_table_s = dict()
        s = s.split()
        if len(s) != len(pattern): return False
        for i in range(len(pattern)):
            p = pattern[i]
            w = s[i]
            if p in hash_table_p:
                if hash_table_p[p] != w:
                    return False
            if  w in hash_table_s:
                if hash_table_s[w] != p:
                    return False
            hash_table_s[w] = p
            hash_table_p[p] = w
        return True