139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

1
2
3

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

1 2	Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false

s = “catsandog”
wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
找字頭符合，在字典標為True.

# T: O(nˆ2), S: O(n)
    def wordBreak(self, s, dict):
        n = len(s)
        f = [False for i in range(n+1)] # 從該位置有無符合的字
        f[0] = True # 第一個字
        for i in range(n):
            if f[i]: # 字頭
                for j in dict: # 找字典有的字
                    l = len(j)
                    if i+l<=n and s[i:i+l] == j:
                        f[i+l] = True # 下一個字
        return f[n]

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)