leetcode : word break 2

한 25분만에 푼거같다. 난이도가 hard인데!

Word Break II - LeetCode

Word Break II - LeetCode

 

DP문제를 이렇게 빨리 풀다니 ㄷㄷ 정말 <Topcoder 알고리즘 트레이닝>이라는 책이 나에게 큰 도움이 된 듯.

 

아이디어는 이렇다.

예를 들어

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

이런 경우에

9번째 글자까지 묶는 경우는  총 2가지다. ["pineapple", "pine apple"]

10번째 글자부터 스캔을 했더니 "pen"이라는 글자가 발견되었다.

그럼 12번째 글자까지 묶는 경우는 ["pineapple", "pine apple"]의 원소들에 "pen"을 각각 붙인

["pineapple pen","pine apple pen"]이 된다.

 

즉 임의의 인덱스 i에 대해서 s[:i]까지 묶는 모든 경우를 담은 리스트가 있으면

s[i]에서 단어를 하나 발견했을 때

발견한 단어를 이전의 리스트 모든 원소에 추가해주면 된다는 것이다.

지금까지 계산한 결과를 바탕으로 다음 step의 계산결과를 만드니까 이것은 영락없는 dp다!

 

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        dp = [[] for _ in range(len(s) + 1)]
        
        wdict = set()
        for word in wordDict:
            wdict.add(word)
        
        for i in range(len(s)):
            for j in range(1,11):
                if i+j > len(s):
                    continue
                
                word = s[i:i+j]
                if word in wdict:
                    if not dp[i] and i == 0:
                        dp[i+j].append(word)
                    else:
                        for previous in dp[i]:
                            dp[i+j].append(previous + " " + word)
        
        return dp[len(s)]