139. 单词拆分 - 力扣（LeetCode）
给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入:s = "leetcode", wordDict = ["leet", "code"]输出:true解释:返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入:s = "applepenapple", wordDict = ["apple", "pen"]输出:true解释:返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。
示例 3：
输入:s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]输出:false
解题思路：
定义dp[i]表示：字符串s的前 i 个字符（即子串s[0..i-1]）能否由字典中的一个或多个单词拼接而成。
显然dp[0] = true，表示空串可以被拼出（作为递推的起点）。
对于i从 1 到n（n = s.length()），我们枚举最后一个单词的起始位置 j（0 ≤ j < i）：
如果
dp[j] == true，说明前j个字符已经能拼出；并且子串
s[j..i-1]也出现在字典中；
那么前i个字符就能拼出，即dp[i] = true。
dp[j]&&wordDictSet.contains(s.substring(j,i)动态规划五部走：
1. 状态表示dp[i]表示：字符串s的前 i 个字符（即子串s[0..i-1]）能否由字典中的一个或多个单词拼接而成。
2. 状态转移方程
dp[i] = true，当且仅当存在某个 j（0 ≤ j < i），使得：
dp[j] == true 且 s[j..i-1] 在 wordDict 中
3. 初始化
dp[ 0 ] = true 表示空字符串在字典中
4. 填表顺序
由于dp[i]只依赖下标比i小的状态，所以可以从前往后依次填表
5. 返回值
dp[ s.length() ]
class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> wordDictSet = new HashSet(wordDict); boolean[] dp = new boolean[s.length()+1]; dp[0] = true; for(int i=1;i<=s.length();i++){ for(int j=0;j<i;j++){ if(dp[j]&&wordDictSet.contains(s.substring(j,i))){ dp[i] = true; break; } } } return dp[s.length()]; } }
