139. Word Break

Description:

Solution:

ex) 

s = "leetcode"

wordDict = ["leet", "code"]

 

In s, we start from the end of the string. 

dp[8] = True

do[7] = False

dp[6] = dp[5] = False

dp[4] = True = dp[4 + 4]

dp[3] = dp[2] = dp[1] = False

dp[0] = True = dp[0 + 4]

 

If dp[0] is True, it means we can break the string with wordDict!