[리트코드] 139. Word Break

# 문제 설명

문자열 s와 문자열들의 사전인 wordDict가 주어질 때, s를 wordDict의 단어들로 분할할 수 있으면 True를 반환해라.

단, wordDict 내의 단어들은 분할에서 여러 번 사용할 수 있다.

 

# 입출력 예시

입력	출력
s = "leetcode" wordDict = ["leet", "code"]	True
s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"]	False

 

# 코드 풀이

틀린 풀이 이지만, 생각했던 방식을 정리해보았다.

 

1. 각 문자마다 wordDict로 시작하는 문자가 있다면, 재귀로 찾아가며 문자열 끝에 도달하면 True를 반환.

from collections import defaultdict

class Solution:    
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        prefix_no = defaultdict(list)
        for word in wordDict:
            prefix_no[word[0]].append(word)
        
        def is_complete(s, i, prefix_no):
            if i == len(s):
                return True
            elif s[i] in prefix_no: # s[i]로 시작하는 문자가 있는지
                for x in prefix_no[s[i]]:
                    if s[i:].startswith(x): # 문자에 해당한다면
                        if is_complete(s, i+len(x), prefix_no):
                            return True
            return False
        return is_complete(s, 0, prefix_no)

 

2. 이전에 풀었던 Trie 자료구조를 사용하기 위해 접근 방법이다.

Trie에 단어들을 모두 저장한 뒤에, 각 문자를 따라 확인해가며 하나의 word가 된다면 q에 저장하여 거기서 부터 다시 탐색할 수 있도록 한다.

만일 입력 문자열이 더 작은 경우에는, q에 문자열의 크기가 저장되어 있을 테니 True를 반환한다.

from collections import deque, defaultdict

class TrieNode:
    def __init__(self):
        self.is_word = False
        self.nexts = defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.trie = TrieNode()
    def insert(self, word: str): 
        head = self.trie 
        for x in word: 
            head = head.nexts[x] 
        head.is_word = True

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        trie = Trie()
        for x in wordDict:
            trie.insert(x)
        
        q = deque([0])
        while q:
            i, head = q.pop(), trie.trie
            for j, c in enumerate(s[i:]):
                if head.nexts[c].is_word: # 다른 길이 있으면
                    q.append(i+j+1)

                if c in head.nexts: 
                    head = head.nexts[c]
                    if head.is_word and not head.nexts: # 끝났으면
                        head = trie.trie
                        q.pop()
                        if i+j == len(s)-1:
                            return True
            if len(s) in q:
                return True
        return head.is_word

 

 

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for i in range(len(s)):
            for j in range(i, len(s)):
                if dp[i] and s[i:j+1] in wordDict:
                    dp[j+1] = True
        return dp[-1]

 

# 핵심 포인트

• wordDict에 있는 단어가 어디에서 끝나는지를 확인하기 위해, 문자열 길이 + 1 만큼의 bool 배열을 만들어주었다.
• wordDict에 있는 단어인지를 확인하기 위해 s[i:j+1]를 사용하였다.

 

참고 링크.
https://leetcode.com/problems/word-break/discuss/43808/Simple-DP-solution-in-Python-with-description

Simple DP solution in Python with description - LeetCode Discuss