单词拆分-动态规划

女爷i 2021-12-05 13:29 312阅读 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 条评论，312人围观）

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

相关阅读

相关 139.单词拆分

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

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

相关 LeetCode_动态规划_343.整数拆分

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个正整数 n ，将其拆分为 k 个正整数的和（k >= 2），并使这些整数的

冷不防/ 2023年10月06日 23:37/ 0 赞/ 17 阅读

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

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

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

相关 LeetCode动态规划完全背包问题——139.单词拆分

题目描述： [139. 单词拆分![icon-default.png?t=M4AD][icon-default.png_t_M4AD]https://leetcode.c

落日映苍穹つ/ 2023年10月03日 19:09/ 0 赞/ 17 阅读

相关 lintcode107. 单词拆分 I动态规划

给定字符串 s 和单词字典 dict，确定 s 是否可以分成一个或多个以空格分隔的子串，并且这些子串都在字典中存在。样例样例 1: 输入: "

偏执的太偏执、/ 2023年07月25日 09:45/ 0 赞/ 98 阅读

相关 139. 单词拆分

题目： [139. 单词拆分][139.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_tex

叁歲伎倆/ 2023年02月21日 02:25/ 0 赞/ 102 阅读

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

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

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

相关 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 赞/ 272 阅读

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

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

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

相关单词拆分-动态规划

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

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