单词拆分-动态规划

女爷i 2021-12-05 13:29 200阅读 0赞

class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            //动态规划 s[i]以i结尾的子串是否满足题干条件
            boolean [] dp=new boolean[s.length()];
            Set<String> set1=new HashSet();
            //把worddict放到字典中
            for(String str:wordDict){
                set1.add(str);
            }
            for(int r=0;r<s.length();r++){
                if(set1.contains(s.substring(0,r+1))){
                    dp[r]=true;
                    continue;
                }
                
                for(int j=0;j<r;j++){
                    if(dp[j]&&set1.contains(s.substring(j+1,r+1))){
                        dp[r]=true;
                        break;
                    }            
                }
            }
            return dp[s.length()-1];
        }
    }

public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> wordDictSet=new HashSet(wordDict);
            boolean[] dp = new boolean[s.length() + 1]; //dp[i] 表示以第i个字符结尾的字符串是否符合要求
            dp[0] = true;
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 0; j < i; j++) {
                    //第 j 个字符的子串和第 j 到 i 的子串都符合要求，返回true
                    if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }

转载于:https://www.cnblogs.com/NeverGiveUp0/p/11146432.html

发表评论取消回复

表情：

评论列表（有 0 条评论，200人围观）

还没有评论，来说两句吧...

相关阅读

相关 139.单词拆分

139.单词拆分题干描述思路背包问题 1. 确定dp数组以及下标的含义 2. 确定递推公式 3. dp数组

你的名字/ 2023年10月16日 17:08/ 0 赞/ 26 阅读

相关 leetcode 139. 单词拆分

递归暴力超时 include <iostream> include <vector> using namespace std;

分手后的思念是犯贱/ 2023年10月10日 10:09/ 0 赞/ 68 阅读

相关 LeetCode_动态规划_中等_139.单词拆分

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以

电玩女神/ 2023年10月06日 22:43/ 0 赞/ 63 阅读

相关 leetcode 139 单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词

叁歲伎倆/ 2023年06月20日 06:26/ 0 赞/ 21 阅读

相关 [Leedcode][JAVA][第139题][单词拆分][递归][记忆优化][动态规划]

【问题描述】\[中等\] 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

ゝ一纸荒年。/ 2023年02月20日 07:48/ 0 赞/ 8 阅读

相关 leetcode 140. Word Break II | 140. 单词拆分 II（动态规划）

题目 [https://leetcode.com/problems/word-break-ii/][https_leetcode.com_problems_word-br

朴灿烈づ我的快乐病毒、/ 2022年08月31日 11:05/ 0 赞/ 169 阅读

相关 leetcode 139. Word Break | 139. 单词拆分（动态规划）

题目 [https://leetcode.com/problems/word-break/][https_leetcode.com_problems_word-break

你的名字/ 2022年08月31日 09:55/ 0 赞/ 185 阅读

相关 leetcode 139 单词拆分

前言题目：[139. 单词拆分][139.] 参考题解：[单词拆分-代码随想录][-] -------------------- 提交代码我没想出来，瞅了

我不是女神ヾ/ 2022年08月28日 03:52/ 0 赞/ 177 阅读

相关【LeetCode】- 139 - 单词拆分

题目描述： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L

悠悠/ 2022年02月23日 10:36/ 0 赞/ 256 阅读

相关单词拆分-动态规划

class Solution { public boolean wordBreak(String s, List<String> wordDict) {

女爷i/ 2021年12月05日 13:29/ 0 赞/ 201 阅读