1 """ 2 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. 3 Note: 4 The same word in the dictionary may be reused multiple times in the segmentation. 5 You may assume the dictionary does not contain duplicate words. 6 Example 1: 7 Input: s = "leetcode", wordDict = ["leet", "code"] 8 Output: true 9 Explanation: Return true because "leetcode" can be segmented as "leet code". 10 Example 2: 11 Input: s = "applepenapple", wordDict = ["apple", "pen"] 12 Output: true 13 Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". 14 Note that you are allowed to reuse a dictionary word. 15 Example 3: 16 Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 17 Output: false 18 """ 19 """ 20 动态规划：类似于322题：https://www.cnblogs.com/yawenw/p/12298704.html 21 方程为dp[i] = { True if dp[:i] in dict 或者 dp[j] if dp[j:i] in dict } 22 传送门：https://blog.csdn.net/daniel_hh/article/details/89575491 23 """ 24 class Solution: 25 def wordBreak(self, s, wordDict): 26 dp = [False] * (len(s) + 1) 27 dp[0] = True 28 if s in wordDict: 29 return True 30 for i in range(1, len(s) + 1): # 从第一个到最后一个字符 31 for j in range(i): # i之前的第一个到i个字符 32 #切片的用法 33 #nums = [2, 5, 8, 4] print(nums[0:3]) == [2, 5, 8] 34 #string = "abcdefg" print(string[5:110]) == 'fg' 35 if dp[j] and s[j:i] in wordDict: # !!!动态方程 36 dp[i] = True 37 break #break 可有可无 38 return dp[len(s)]