⭐️ LeetCode 알고리즘 풀이 (with Python)

# Word Pattern

[Quetion]

LeetCode 290. Word Pattern

📌 접근법

[문제 이해]

• 주어진 pattern과 문자열의 패턴이 같으면 True 아니면 False
• ex) pattern = abba, s = dog cat cat dog

가장 먼저 문자열 구분하기 위해서는 공백을 기준으로 split()하고 pattern을 key 값, value를 문자열로 하는 HashMap의 방법으로 접근했다.

HashMap에서 이미 key가 있으면 반복되는 패턴임을 확인할 수 있고, key의 value와 문자열을 비교하면 패턴이 맞는지 확인하는 조건문으로 구현을 했다.

💻 구현

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        word = s.split(' ')
        w_dict = {}
        # 패턴의 길이와 문자열의 길이 비교
        if len(pattern) != len(word):
            return False
        
        for i, d in enumerate(pattern):
        	# pattern에 해당하는 key가 있을 경우 key와 분리된 문자열 비교  
            if d in w_dict and w_dict[d] != word[i]:
                return False
            
            # key가 없는데 문자열이 HashMap에 있는 경우      
            elif d not in w_dict and word[i] in w_dict.values():
                return False
                
            # pattern을 key, 분리된 문자열을 value로 하는 HashMap 값 생성
            elif d not in w_dict:
                w_dict[d] = word[i]
        return True 

Runtime: 26ms | Memory: 16.2MB
LeetCode 코드 중 Runtime 99%, Memory 85% 해당하는 결과

📌 로직 핵심

• 문자열 s를 공백 기준으로 분리
• enumerate()로 인덱스와 값을 동시에 활용 가능
• pattern을 key로 하고 분리된 문자열을 value로 하는 HashMap
• False의 경우를 분리
• 반복문 내의 조건이 모두 아닌 경우 True

📝 Word Pattern 회고

• 문자열을 분리하는 과정에서 O(N)의 시간복잡도가 발생했고, 모든 문자열이 독립적일 경우 딕셔너리에 문자열 전부를 저장해야하므로 최악의 경우 O(N)의 공간복잡도를 가진다.

• HashMap의 key:value로 바로 접근할 수 있다는 특성을 활용한 간단한 문제였다.

• 문제를 해결하고 솔루션을 참고했을 때 dict를 2개 사용한 코드도 있었고, dict를 사용하지 않은 코드들도 있었다. 그리고 거의 같은 방법으로 접근하여 해결한 코드도 있었다.

• 크게 어려운 문제는 아니었지만 응용되는 문제가 나왔을 때 다른 자료구조와 함께 HashMap의 방법을 잘 사용하는 것이 중요할 것 같다고 생각했다.