[LeetCode]Word Break

https://leetcode.com/problems/word-break/description/

Word Break - LeetCode

 

문제 분석

문자열 s와 단어 집합인 wordDict가 주어진 경우에, 문자열 s를 wordDict 만으로 분해할 수 있는지 구하는 문제입니다.

wordDict는 재사용이 가능하고 띄어쓰기 만으로 s가 분해가 되는지 확인하는 문제입니다.

 

처음 시도한 답안 - 실패, DFS, Time Limit

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:

        d = []
        def dfs(s, wordDict, char):
            if len(s) < len(char):
                return

            if char == s:
                d.append(True)

            for idx in range(len(wordDict)):
                dfs(s, wordDict, char+wordDict[idx])

            # return Tru

        a = dfs(s, wordDict, '')
        
        return any(d)

접근 방법

1. DFS를 사용한 풀이입니다. 시간 초과로 실패했습니다.
2. dfs 내부에서
   1. 누적시킨 char의 길이가 문자열보다 길다면 Return 합니다.
   2. 누적시킨 char의 길이가 주어진 문자열과 같다면 True를 리스트에 추가합니다.
   3. wordDict가 가진 단어의 갯수만큼 순회합니다.
      
      1. 주어진 wrodDict를 char에 더해서 문자열을 완성시켜나가는 재귀 호출을 수행합니다.
3. 반복을 완료하고 하나라도 True가 담겨있다면 True를 리턴합니다.

해당 풀이는 테스트 케이스는 맞출 수 있었지만, 재귀 호출하는 횟수가 너무 많아서 Time Limit Exceeded에 걸리게 되었습니다. 그래서 DFS에 memoization을 활용해 이미 계산된 결과는 다시 활용할 수 있도록 개선해보았습니다.

 

두번째로 시도한 답안 - 성공, DFS with memoization

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        memo = {}
        
        def dfs(start):
            # 이미 있는 결과라면 활용하기.
            if start in memo:
                return memo[start]

            # wordDict의 값으로 s를 만들었다면 True.
            if start == len(s):
                memo[start] = True
                return True

            # start값을 가지고 wordDict를 매번 순회해보면서
            for word in wordDict:
                if s[start: start+len(word)] == word:
                    # wordDict만으로 완성이 된 경우라면 True
                    if dfs(start+len(word)):
                        memo[start] = True
                        return True

            memo[start] = False
            return False      
        
        return dfs(0)

접근 방법

1. 첫번째와 같이 동일하게 DFS를 활용해 풀이합니다.
2. dfs 내부에서
   1. start 변수는 wordDict로 조합한 누적 문자열의 길이입니다. 
   2. 이미 있는 결과라면 memo에 담긴 값을 활용합니다.
   3. start 값이 s의 길이와 동일하다면 문자열이 완성이 된 것입니다. 따라서 완성 결과를 memo에 기록하고 True를 리턴합니다.
   4. wordDict를 순회하면서
      1. 주어진 시작 지점부터 보았을 때 등장한 문자와 동일하다면
         1. dfs에 시작지점+등장한 word 단어수로 호출합니다.
            1. 호출한 결과가 True라면 memo에 기록하고 True를 리턴합니다.
   5. 모두 순회했는데도 만들 수 없었다면 memo에 False를 기록하고 False를 리턴합니다.

시작 지점을 key로 하여 True, False를 value로 기록해둔다면 똑같은 시작지점인 경우에는 기억된 값을 활용할 수 있습니다. 따라서 추가로 탐색하지 않게 됩니다. 

깊이 탐색으로 진행하기 때문에 wordDict에 같은 길이의 문자열이 존재하더라도 먼저 True가 발견되면 Return하고 종료하게 됩니다. 따라서 memo의 키값이 같은 상황에서 값이 달라질 수 있는 것은 문제가 되지 않습니다.

 

세번째로 시도한 답안 - 성공, DP

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False for _ in range(n+1)]
        dp[0] = True

        for i in range(1, n+1):
            for j in range(i): 
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
            

        return dp[-1]

접근 방법

1. 마지막은 DP를 활용한 풀이입니다.
2. 문자열의 길이 +1 만큼 dp를 할당합니다. dp[0]는 True로 할당합니다.
3. 이중 순회를 반복합니다. 두번째 반복은 i번째 까지만 반복합니다.
   1. s[j:i]로 슬라이싱한 단어가 wordDict에 존재하는지 검사합니다.
   2. 시작한 j 지점이 True인지 확인합니다.
      1. 모두 True라면 dp[i]를 True로 설정하고 반복을 빠져나옵니다.
4. 순회를 마치면 가장 마지막 요소를 리턴합니다.

DP의 요소가 True가 되었다는 것은 해당 글자수를 만드는데에 wordDict로 구성이 되었다는 것을 의미합니다.

예시를 들어 설명해보겠습니다.

 

s = "leetcode", wordDict = ["leet", "code"]

dp[0] = True, 글자의 길이가 0인 경우는 True로 간주합니다.

dp[1] = False, wordDict에 "l" 단어는 없습니다.

dp[2] = False, wordDict에 "le" 단어는 없습니다.

dp[3] = False, wordDict에 "lee" 단어는 없습니다.

dp[4] = True, wordDict에 "leet" 단어는 있습니다.

dp[5] = False, wordDict에 "leetc", "eetc", "etc", "tc", c" 어느 단어도 없습니다.

dp[6] = False, wordDict에 "leetco", "eetco", "etco", "tco", "co", "c" 어느 단어도 없습니다.

dp[7] = False, wordDict에 "leetcod", "eetcod", "etcod", ..., "od", "d" 어느 단어도 없습니다.

dp[8] = True, wordDict에 "leetcode", ..., "tcode"는 없지만, "code" 단어는 있습니다.

 

따라서 마지막 DP의 요소는 True가 됩니다. 부연 설명을 하자면 이중 포문에서 j가 반복되면서 "leetcode", "eetcode", ..., "tcode", "code" 처럼 문자열을 슬라이싱하는 역할을 하게 됩니다.

또한, dp[8]에서 "code"가 wordDict에 있는 경우에 "leet"인 dp[4]가 True인 조건도 같이 고려해야합니다.

 

다양한 풀이 방법이 있었는데 DP 방식이 이해하기에는 가장 어려웠던 것 같습니다. 개인적으로는 wordDict 문자들을 재귀 호출해 누적시키면서 s를 만들어가는 것이 조금 더 자연스러운 사고 방식이었던 것 같습니다.