leetcode139. 单词拆分(dp)

oldwong77

于 2021-06-11 09:11:23 发布

阅读量293

点赞数

分类专栏： leetcode

本文链接：https://blog.csdn.net/qq_37360631/article/details/117804911

版权

leetcode 专栏收录该内容

32 篇文章

订阅专栏

本文介绍了一种使用动态规划解决字符串划分问题的方法。通过判断一个字符串是否能由给定词典中的单词组合而成，实现了一个名为wordBreak的功能。此方法采用完全背包思想，允许词典中的单词重复使用。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

在这里插入图片描述

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        // 完全背包问题
        // 每个单词可以选择无数次
        // dp[i]表示下标为i-1结尾的string，能否被dict划分
        boolean[] dp = new boolean[len+1];
        dp[0] = true;
        for(int i=1;i<=len;i++){
            for(int j=0;j<i;j++){
                if(dp[j] && wordDict.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}