[LeetCode] Word Break II 풀이 - (python 파이썬)

사용 언어: Python 파이썬

문제: https://leetcode.com/problems/word-break-ii/

Word Break II - LeetCode

이 문제는 Word Break(Medium)과 연관된 문제로, 좀 더 난이도가 높은 문제이다. Word Break의 해설은 여기서 볼 수 있다.

 

이 문제의 핵심은 Memoization이다.

Memoization은 동일한 계산을 반복할 때, 이전의 값을 메모리에 저장하여 반복 수행을 제거하는 방법이다. 주어진 테스트 케이스는 통과하는데 제출을 하면 시간 초과가 나서 뭐가 문제인가 검색해보니 Memoizaiton이었다.

 

먼저, 주어진 문제를 읽어보자.

Input

- non-empty 문자열 s

- non-empty 단어들을 담고있는 딕셔너리 wordDict (중복된 단어는 주어지지 않는다.)

 

Output

wordDict의 단어들로 문자열 s를 만들 수 있는 모든 조합을 찾아서 출력해라

 

주어진 예시는 다음과 같다.

Input: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"]

Output: [   "cats and dog",   "cat sand dog" ]

 

Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]

Output: [   "pine apple pen apple",   "pineapple pen apple",   "pine applepen apple" ]

 

 

1. 주어진 문자열 s가 word로 시작하는지 확인

2. 시작한다면 문자열 s에서 word를 제외한 나머지 부분 문자열을 sub 변수에 저장한다. 

3. 1번의 s에 sub을 넣어 나머지 부분 문자열이 ""가 될 때까지 반복한다.

4. wordDict에 속한 word들을 1~3번 과정을 반복시키며 정답을 찾는다.

 

첫 번째 예시를 보자.

s = "catsanddog"

wordDict = ["cat", "cats", "and", "sand", "dog"]

 

cat -> 나머지 문자열(sanddog)

cat -> sand -> 나머지 문자열(dog)

cat -> sand -> dog -> 나머지 문자열("")

정답: "cat sand dog"

 

cats -> 나머지 문자열(anddog)

cats -> and -> 나머지 문자열(dog)

cats -> and -> dog -> 나머지 문자열("")

정답: "cats and dog"

 

이걸 그대로 코드로 옮겨보자

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        
        return self.helper(s, wordDict)
        
    def helper(self, s, wordDict):
        results = []

        if (len(s) == 0):
            results.append("");
            return results

        for word in wordDict:
            if not s.startswith(word):
                continue
            
            if len(word) == len(s):
                results.append(word)

            else:
                sub = s[len(word):]
                substring = self.helper(sub, wordDict)

                for substr in substring:
                    if not substr:
                        results.append(word + "" + substr)
                    else:
                        results.append(word + " " + substr)

        return results

이렇게 할 경우 테스트 케이스는 통과하지만 제출해보면 시간 초과라며 해당 케이스를 알려준다.

총 36개의 tc중 5개가 통과하지 못했다. 같은 연산을 계속 반복하다보니, 시간 초과가 난다. 이때 사용해야하는 것이 Memoization이다. 나머지 부분 문자열의 모든 경우의 수를 memo에 저장하여 더 이상 탐색하지 않도록 하면 된다.

 

Memoization을 쓴 최종 코드는 다음과 같다.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        
        return self.helper(s, wordDict, {})
        
    def helper(self, s, wordDict, memo):
        if s in memo: return memo[s]
        if not s: return []

        results = []

        if (len(s) == 0):
            results.append("");
            return results

        for word in wordDict:
            if not s.startswith(word):
                continue
            
            if len(word) == len(s):
                results.append(word)

            else:
                sub = s[len(word):]
                substring = self.helper(sub, wordDict, memo)

                for substr in substring:
                    results.append(word + " " + substr)

        memo[s] = results
        return results

 

문자열 s = "catsanddog"에 직접 대입해보자.

s = "catsanddog"

helper("catsanddog", wordDict, {})

 

wordDict의 word "cat"으로 시작

sub = "sanddog"

substring = helper("sanddog", wordDict, {})

    s = "sanddog"

    word = "sand"

    sub = "dog"

        substring = helper("dog", wordDict, {})

        "dog"과 wordDict의 "dog"이 같으므로 results = ['dog'], memo = {'dog': ['dog']}

    results = ["sand dog"] -> memo = {'dog': ['dog'], 'sanddog': ['sand dog']}

results = ["cat sand dog"] 반환

 

wordDict word "cats"로 시작

sub = "anddog"

substring = helper("anddog", wordDict, {'dog': ['dog'], 'sanddog': ['sand dog']})

    s = "anddog"

    word = "and"

    sub = "dog" -> memo에 있으므로 ['dog'] 반환

    results = ["and dog"] -> memo = {'dog': ['dog'], 'sanddog': ['sand dog'], 'anddog': ['and dog']}

results = ["cats and dog"] 반환

 

Memoization을 처음 활용해봐서 그런지 조금 어려웠다.

아래 영상은 이 문제를 잘 설명해놓은 풀이라 참고하면 좋을 것 같다.

https://www.youtube.com/watch?v=uR3RElKnrkU