Leetcode: Word Break

Word Break I

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.
Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

 

문자열 s와 단어들의 리스트 wordDict가 input으로 들어왔을 때, wordDict 안에 있는 단어들로 s를 구성할 수 있는지 묻는 문제이다. dynamic programming을 이용해 해결하였다.

 

from typing import List
from collections import defaultdict


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False for _ in range(len(s))]
        word_d = defaultdict(list)
        for word in wordDict:
            word_d[word[0]].append(word)

        for i in reversed(range(len(s))):
            if s[i] not in word_d:
                continue
            for word in word_d[s[i]]:
                if s[i:].startswith(word):
                    if i + len(word) == len(s):
                        dp[i] = True
                    elif i + len(word) < len(s):
                        dp[i] = dp[i + len(word)]
                    else:
                        dp[i] = False
                    if dp[i]:
                        break
        return dp[0]

dp문제를 풀 때에는 항상 아래와 같은 스텝을 밟으며 문제를 해결한다.

 

1. dp[i]가 의미하는 바: s의 i번째 index부터 (s[i:])의 문자열이 wordDict에 있는 단어들로 구성이 가능한가? (True / False)

2. dp[i]를 initialize하는 방법: 모두 False로 initialize

3. dp[i]의 점화식:

- i + wordDict에서 찾은 단어의 길이가 s의 길이와 동일한 경우: word == s[i:]라는 의미이므로, True

- i  + wordDict에서 찾은 단어의 길이가 s의 길이보다 작은 경우: s[i:i+len(word)] == word이고, dp[i]는 s[i+len(word)]가 wordDict에 있는 단어로 구성이 가능한지에 따라 결정된다 -> dp[i] = dp[i+len(word)]

- 이외의 경우: False

4. dp[i]를 채우는 순서: len(s)-1 downTo 0

5. 정답이 의미하는 바: dp[0] == True

 

wordDict를 순회할 때에, 가능하면 한 번에 탐색할 단어의 갯수를 줄이기 위해 wordDict를 첫글자를 기준으로 grouping했고, 이 때 python의 defaultdict를 사용하며 리스트를 순회하며 딕셔너리에 추가하였다. groupby를 이용해도 될 듯 하다. 

s의 마지막 index부터 0까지 순회하며 해당 점화식을 적용하면 정답이 나온다. 

 

링크: leetcode.com/problems/word-break/submissions/

Word Break - LeetCode

 

Word Break II

여기서 한 단계 더 진화한 문제로, Word Break II가 있다. 위의 문제와 거의 동일하지만, 위에서는 해당 s가 word break될 수 있는지 없는지의 여부만 리턴하면 되었다면, 이번에는 단어의 조합들을 리턴해주어야 한다. 이를 위해, 기존 dp array에 True, False만 입력하는 것이 아니라, 단어를 저장하도록 변경하였다. 

처음에는 아래와 같이 구현하였는데, 특정 input에서 Time limit exceeded가 발생했다.

from typing import List
from collections import defaultdict


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        word_d = defaultdict(list)
        for word in wordDict:
            word_d[word[0]].append(word)

        dp = [[] for i in range(len(s))] # dp[i]: i번째 index가 word break 가능한 경우, 사용된 word list들의 모음
        for i in reversed(range(len(s))):
            for word in word_d[s[i]]:
                if s[i:].startswith(word):
                    if i + len(word) == len(s):
                        dp[i].append([word])
                    elif i + len(word) < len(s) and dp[i+len(word)]:
                        for comb in dp[i+len(word)]:
                            dp[i].append([word] + comb)
                            
        return map(lambda x: " ".join(x), dp[0])
        
---------------------------------------------------------------------------------------
        
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
        
Time Limit Exceeded

위의 코드에서 dp[i]가 의미하는 바는, s[i:]를 word break했을 때의 결과물이다. 즉 dp[i]가 문자열 리스트의 리스트이고, 마지막에 dp[0]만 stringify해서 return하면 된다. 이를 위해, s[i:]가 특정 word로 시작하는 경우, dp[i]는 해당 dp[i+len(word)]의 각 리스트에 word를 더한 것이 된다. 이 부분에서 불필요하게 순회가 많이 발생하게 된다.

예를 들어 위의 예시와 같은 경우, 각 dp[i]에 굉장히 많은 경우의 수가 발생하고, 그것이 i가 작아질수록 누적되므로 dp[i]의 길이가 매우 길어진다. 그러나, 이 dp[i]가 실제로 사용될지는 알 수 없다. 실제로 위와 같은 경우, 주어진 word들은 모두 a로 구성되어있으나 string에 b가 껴있으므로 정답은 []이다. 이 경우 string의 b부분을 보기 전까지 불필요하게 순회가 많이 발생하게 된다.

이같은 상황을 방지하기 위해, dp[i]에는 s[i:].startswith()이 True가 된 단어들만 저장하고, 마지막에 dp[0]부터 recurvise하게 호출하며 결과를 만들어가도록 변경하였다.

from typing import List
from collections import defaultdict


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        word_d = defaultdict(list)
        for word in wordDict:
            word_d[word[0]].append(word)

        dp = [[] for i in range(len(s))] # dp[i]: i번째 index가 word break 가능한 경우, s[i:].startswith()이 True인 word의 모음
        for i in reversed(range(len(s))):
            for word in word_d[s[i]]:
                if s[i:].startswith(word):
                    if i + len(word) == len(s):
                        dp[i].append(word)
                    elif i + len(word) < len(s) and dp[i+len(word)]:
                        dp[i].append(word)

        def dfs(idx: int) -> List[List[str]]:
            result = []
            for word in dp[idx]:
                if idx+len(word) == len(s):
                    result.append([word])
                else:
                    for next_words in dfs(idx+len(word)):
                        result.append([word] + next_words)

            return result

        return map(lambda x: " ".join(x), dfs(0))

위와 같이 마지막에 정답을 뽑아낼 때에만 recursive하게 각 리스트를 순회하도록 변경하였더니, time limit이 발생하지 않았다. 

 다만, 아래와 같은 input이 들어왔을 때에는 여전히 Time limit이 발생하게 된다.

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

실제로 해당 문자열은 주어진 word들로 구성이 가능하고, 그 경우의 수가 아주 많다. 이 경우, leetcode에서 test를 돌려봐도 expected result에 아무 값이 표시되지 않는 것으로 보아, leetcode의 프로그램도 정답을 내지 못하는 듯 보였다. 실제로 경우의 수가 너무 많아서 그런 것 같다.