北太平庄网站建设,专业的公司网站开发,上海中高风险地区名单,网站建设网页设文章目录题目描述思路 代码二刷更新题目描述
漏网之题。。一个月前写的居然没写博客
思路 代码
HashSet 存储 word#xff0c;便于查询动态规划三要素在注释中思路#xff1a;如果dp[j] true且[j1,i]可以组成单词#xff0c;则dp[i] true
class Solution…
文章目录题目描述思路 代码二刷更新题目描述
漏网之题。。一个月前写的居然没写博客
思路 代码
HashSet 存储 word便于查询动态规划三要素在注释中思路如果dp[j] true且[j1,i]可以组成单词则dp[i] true
class Solution {// 判断当前字符串能否被word组成public boolean wordBreak(String s, ListString wordDict) {// dpdp[i]代表[0,i-1]的子字符串能否被完整拆分// dp[i]如何判定用j划分[0,j][j1,i]如果dp[j] true且[j1,i]可以组成单词则dp[i] trueint len s.length();boolean[] dp new boolean[len 1];// 建立一个哈希表方便查找是否存在SetString set new HashSet();for(int i 0; i wordDict.size(); i){set.add(wordDict.get(i));}// 为了边界默认空字符串为truedp[0] true;for(int i 1; i len; i){for(int j 0; j i; j){// 状态转移方程可以组成的情况// 最优子结构dp[j]if(dp[j] set.contains(s.substring(j,i))){dp[i] true;break;}}}return dp[len];}
}二刷更新
最优子结构前面的子串结果当前转移前面某子串满足而且剩下的子串也在 Set 内
class Solution {public boolean wordBreak(String s, ListString wordDict) {SetString set new HashSet();for(String temp : wordDict) {set.add(temp);}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] set.contains(s.substring(j, i))) {dp[i] true;break;}}} return dp[s.length()];}
}
