LeetCode139 单词拆分

题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2:
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
	 注意,你可以重复使用字典中的单词。
示例 3:
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同

方法

动态规划

dp[i]表示从0到i-1的字符串是否能够由字典的字符子串拼成,因此
dp[i] = dp[j]&&check(j,i-1),其中0<j<i,check(j,i-1)表示从j到i-1截出的字符子串是否在字典里

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(n)
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int length = s.length();
        Set<String> set = new HashSet(wordDict);
        boolean[] dp = new boolean[length+1];
        dp[0] = true;
        for(int i=1;i<=length;i++){
            for(int j=0;j<i;j++){
                if(dp[j]&&set.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[length];
    }
}

推荐这些文章:

139. 单词拆分

完全背包
import java.util.List;

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

/**
* dp[j]定义为长度为j的字符串是否可以由字典中的子串组成...

343. 整数拆分(dp)

 
难度中等668

给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 ...

Leetcode 139. 单词拆分 dp

地址 https://leetcode-cn.com/problems/word-break/
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例 1:
输入: s = "leetcode"...

【动态规划】力扣139:单词拆分()

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 ...

Leetcode 139. 单词拆分 中等 动态规划

139. 单词拆分
题目:
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
输入: s = "leetcode", wordDict = ["leet", "code"]输出: true...

poj3230Travel(dp动态规划)

题目链接:http://poj.org/problem?id=3230

1 #include<iostream>
2 #include<algorithm>
3 #include<cmath>
4 #include<cstring>
5 #include<cstdio&g...

Leetcode72/583之动态规划中的编辑距离

编辑距离

涉及到字符串的插入,删除,替换
注意ij和i-1 j-1以及i-1 j 或者i j-1之间的关系就行了

Leetcode72-编辑距离

给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:

插入一个字符
删除一个字符
替换一个字...

2022-3-31 高频题 day4

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

1 class Solution {
2 p...

Leetcode518/322/139之完全背包类型的例题

完全背包类型的例题
Leetcode518-零钱兑换二

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。
假设每一种面额的硬币有无限个。
输入:amount = 5, coins = [1, 2, 5]
...

LeetCode-139. 单词拆分

题目来源
139. 单词拆分
题目详情
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意: 不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"]...

文章标题:LeetCode139 单词拆分
文章链接:https://www.dianjilingqu.com/4219.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>