力扣热门100题之单词拆分

张开发
• 2026/4/16 10:40:36 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

力扣热门100题之单词拆分
核心思路dp[i]表示字符串前 i 个字符能不能被字典里的单词拼出来我们要算的就是dp[s.length()]转移方程如果存在一个位置j满足dp[j] true前 j 个字符能拼出来s[j ... i-1]这个子串在字典里那么dp[i] true通俗解释把字典放进Set方便快速查找dp[0] true空字符串默认是合法的对每个位置i往前看所有j如果前面j是通的并且j 到 i这一段正好是一个单词那i也是通的最后看整个字符串dp[n]是不是通的完整代码实现class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString set new HashSet(wordDict); int n s.length(); boolean[] dp new boolean[n 1]; dp[0] true;// 前0个字符 空串 是可以拼出来的 for(int i 1;in;i){ for(int j 0;ji;j){ // 前j个可以拼 并且j~i这段是单词 if(dp[j] set.contains(s.substring(j,i))){ dp[i] true; break; } } } return dp[n]; } }

更多文章