[LeetCode] 139. Word Break

139. Word Break

Medium

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

 

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

 

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

---

문제 풀이

• 단어 사전에 들어있는 단어들로 중복되지 않게 문장을 완성할 수 있는지 확인하는 문제이다. 
• 사전에 있는 단어를 다중 사용할 수 있으며, 주어진 문장을 사전의 단어들로 구성할 수 있으면 True를 반환한다.
• 제한 조건은 문장의 길이는 최대 300, 단어 사전의 개수는 총 1000개가 될 수 있다.
• 완전탐색으로 풀수 있는 제한 사항이다.

DFS + Memoization

• 단어 사전을 Set으로 변환하고, 해당 인덱스에 사전 단어가 들어있는지 확인할 수 있는 memo 배열을 생성한다.
• 재귀 함수를 호출 했을때 첫 시작 인덱스부터 가장 문장의 마지막 인덱스까지 반복문을 돌면서 사전에 있는 단어인지 확인한다. 
• 그리고 재귀 호출의 반환값도 True라면 주어진 문장의 모든 단어들은 사전의 단어들로 중첩 없이 생성할 수 있다.
• Bottom-Up 방식이라고 보면 이해하기 쉬운데, 우선 가장 마지막 알파벳에서부터 차례대로 탐색하여 
• 메모 배열에 단어가 존재하는지 저장한다. 
• 재귀 함수가 반환이 되면서 그 이전 인덱스로 돌아가게되면, 시작 인덱스부터 아까 확인했던 시작인덱스까지 단어를 검색한다. 
• 다시말해 이전 단계에서 s1 ~ e1 까지의 단어를 검색하고 현재 단계에서 s2 = (e1 + 1) 에서 단어가 존재하는 것이 확인이 된다면
• memo[s2] 에는 True가 저장된다. 
• s1 재귀 함수로 돌아왔을때, s1과 e1사이에는 여러 인덱스가 있지만 만일 s1 ~ e1에 한개의 단어가 존재한다면 s2부터 검색했던 재귀 함수에서 이미 저장한 memo[s2]값을 가져와 사용한다. 
• 정리해서 말하자면, [0, 1, 2, 3, 4] 문장에서 0 ~ 2사이의 3글자 단어가 존재하면 3에 존재하는 단어가 있는지 확인하고 만약 존재한다면, 재귀함수가 반환을 하면서 memo[3] = True, memo[0] = True가 저장된다. 
• 반대로 0 ~ 2사이의 단어가 존재하고 2 ~ 4 사이의 단어가 존재한다면, memo[2] = True 이지만, memo[3]는 False가 된다. 
• 그리고 나서 초기 0번에서 단어를 찾을때, 0 ~ 2사이의 단어를 찾아서 memo[3]으로 들어가게 된다면 얻는 값은 False가 된다. 
• 즉 memo[0]은 False가 된다. 

BFS

• DFS와는 다르게 모든 위치의 단어들을 찾을 필요없이, 문장이 완성되면 코드를 끝내게 되기 때문에 memoization이 필요가 없다. 
• DFS + Memoization과 BFS 모두 O(n^3)이 걸린다. 
• BFS를 수행하면서 현재 위치 인덱스에서 가능한 모든 사전 단어의 끝 위치를 큐에 넣는다. 
• 이렇게 하면, 해당 인덱스에서 사전 단어 길이까지의 확인작업이 보장된다. 
• 그리고 사전 단어들을 모두 탐색하여, 현재위치가 문장의 길이를 넘는다면 이때 정답을 출력한다. 

Dynamic Programming

• 자세히 살펴보면 이문제의 동적프로그래밍 해결법은 BFS 방법과 비슷하다고 생각할 수 잇다. 
• dp 배열을 만들고 첫번째 자리는 True로 저장한다. 
• 모든 인덱스를 탐색하면서 검색이되는 사전 단어가 있는지 dp 배열에 저장하는 방식이다. 
• 즉, 첫번째 반복문의 인덱스는 가장 해당 단어의 마지막을 나타내고 
• 두번째 반복문은 0인덱스 부터 i까지의 단어가 존재하는지 일일이 확인하는 것이다. 
• 매번 단어를 확인할때마다 dp 배열에 해당위치 인덱스에 단어가 있었는지 저장하고, 다음번 단어를 찾을때 이전 dp 위치 인덱스에 단어가 없다면 건너뛴다. 
• dp[j]의 if문에서 선처리가 되기때문에 단어 사전에서 단어를 더 찾아보는 시간이 줄게 된다. 

소스 코드

DFS + Memoization

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # dfs + memo
        memo = [-1] * len(s)
        wordSet = set(wordDict)
        def rec(s, wordSet, start):
            if start == len(s):
                return True
            if memo[start] != -1:
                return memo[start]
            for end in range(start + 1, len(s) + 1):
                if s[start:end] in wordSet and rec(s, wordSet, end):
                    memo[start] = True
                    return True
            memo[start] = False
            return False
        return rec(s, wordSet, 0)

BFS

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # BFS
        q = []
        wordSet = set(wordDict)
        visited = set()
        q.append(0)
        while q:
            cur = q.pop(0)
            if cur in visited:
                continue
            for end in range(cur + 1, len(s) + 1):
                if s[cur:end] in wordSet:
                    q.append(end)
                    if end == len(s):
                        return True
                visited.add(cur)
        return False

Dynamic Programming

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