单词拆分的动态规划解法

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 到nn s.length()我们枚举最后一个单词的起始位置 j0 ≤ 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当且仅当存在某个 j0 ≤ 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, ListString wordDict) { SetString wordDictSet new HashSet(wordDict); boolean[] dp new boolean[s.length()1]; dp[0] true; for(int i1;is.length();i){ for(int j0;ji;j){ if(dp[j]wordDictSet.contains(s.substring(j,i))){ dp[i] true; break; } } } return dp[s.length()]; } }