[LeetCode][Python3] 139. Word Break

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가 반환된다.