Problem :

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


My Solution :

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


Comment :

Example 2가 진행되는 과정을 풀어보면 


s = "applepenapple", wordDict = ["apple", "pen"]


dp = [True, False, False, False, False, False, False, False, False, False, False, False, False, False]


i == 5 and j == 0 일때 dp[0] == True and s[0:5] == "apple" 이 되어 dp[5] = True로 바뀐다.


dp = [True, False, False, False, False, True, False, False, False, False, False, False, False, False]


i == 8 and j == 5 일때 dp[5] == True and s[5:8] == "pen" 이 되어 dp[8] = True로 바뀐다.


dp = [True, False, False, False, False, True, False, False, True, False, False, False, False, False]


i == 13 and j == 8 일때 dp[8] == True and s[8:13] == "apple" 이 되어 dp[13] = True로 바뀐다.


dp = [True, False, False, False, False, True, False, False, True, False, False, False, False, True]


따라서 dp의 마지막 값인 True가 반환된다.