草庐IT

leetcode 139. Word Break 单词拆分(中等)

okokabcd 2023-03-28 原文

一、题目大意

标签: 动态规划

https://leetcode.cn/problems/word-break

给你一个字符串 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 中的所有字符串 互不相同

二、解题思路

这道题的分割条件由集合内的字符串决定，因此在考虑每个分割位置时，需要遍历字符串集合，以确定当前位置是否可以成功分割，注意对于位置0，需要初始化值为真。

三、解题方法

3.1 Java实现

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (String tmp : wordDict) {
                int len = tmp.length();
                if (i>=len && tmp.equals(s.substring(i - len, i))) {
                    dp[i] = dp[i] || dp[i - len];
                }
            }
        }
        return dp[n];
    }
}

四、总结小记

  • 2022/6/24 又到周五了，双休的日子时间飞快
单词leetcodewordDictstrongblockquote算法与数据结构

有关leetcode 139. Word Break 单词拆分(中等)的更多相关文章

  1. ruby - 如何在 Ruby 中拆分参数字符串 Bash 样式？ - 2

    我正在为一个项目制作一个简单的shell，我希望像在Bash中一样解析参数字符串。foobar"helloworld"fooz应该变成:["foo","bar","helloworld","fooz"]等等。到目前为止，我一直在使用CSV::parse_line，将列分隔符设置为""和.compact输出。问题是我现在必须选择是要支持单引号还是双引号。CSV不支持超过一个分隔符。Python有一个名为shlex的模块:>>>shlex.split("Test'helloworld'foo")['Test','helloworld','foo']>>>shlex.split('Test"

  2. ruby-on-rails - 在 ruby​​ 中使用 gsub 函数替换单词 - 2

    我正在尝试用ruby​​中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案 啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了

  3. ruby - 正则表达式将非英文字母匹配为非单词字符 - 2

    @raw_array[i]=~/[\W]/非常简单的正则表达式。当我用一些非拉丁字母(具体来说是俄语)尝试时，条件是错误的。我能用它做什么？ 最佳答案 @raw_array[i]=~/[\p{L}]/使用西里尔字符进行测试。引用:http://www.regular-expressions.info/unicode.html#prop 关于ruby-正则表达式将非英文字母匹配为非单词字符，我们在StackOverflow上找到一个类似的问题： https://

  4. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  5. ruby - 如何在 Cucumber 步骤定义中使单词可选？ - 2

    我在下面有一个步骤定义，它执行我想要它执行的操作，即它根据“PAGES”哈希的“page”元素检查页面的url。Then(/^Ishould(still)?beatthe"(.*)"page$/)do|still,page|BROWSER.url.should==PAGES[page]end步骤定义用于两者我应该在...页面我应该还在...页面但是，我不需要将“still”传递到block中。我只需要它是可选的以匹配步骤但不传递到block中。我该怎么做？谢谢。 最佳答案 您想将“静止”组标记为非捕获。这是通过使用?:启动组来完成的

  6. ruby - 拆分字符串并分配给不同的变量 - 2

    我从ui中得到日期范围为-approved_between"=>"2013-03-17-2013-03-18"我需要拆分此approved_start_date="2013-03-17"和approved_end_date="2013-03-18"...我希望使用它在mysql中查询，因为mysql中的日期格式是created_at:2012-07-2810:35:01.我正在做的是:approved=approved_between.split("")approved_start_date=approved[0]approved_end_date=approved[2]很确定这不是处

  7. ruby-on-rails - Ruby on Rails 将列表拆分或切片为列 - 2

    @locations=Location.all#currentlistingall@locations=Location.slice(5)orLocation.split(5)使用Ruby，我试图将我的列表分成4列，每列限制为5个；然而，切片或拆分似乎都不起作用。知道我可能做错了什么吗？任何帮助是极大的赞赏。 最佳答案 您可能想使用in_groups_of:http://railscasts.com/episodes/28-in-groups-of这是RyanBates在railscast中的示例用法:

  8. ruby - 格式化数字以每隔三位数拆分一次 - 2

    我想在格式化数字时每隔三个字符放置一个空格。根据这个规范:it"shouldformatanamount"dospaces_on(1202003).should=="1202003"end我想出了这段代码来完成这项工作defspaces_onamountthousands=amount/1000remainder=amount%1000ifthousands==0"#{remainder}"elsezero_padded_remainder='%03.f'%remainder"#{spaces_onthousands}#{zero_padded_remainder}"endend所以我

  9. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  10. ruby - 如何对 ruby​​ 中的重音单词数组进行排序 - 2

    如何根据变量alpha的每个字母对重音单词数组进行排序。下面的代码只引用了第一个字母的alpha，所以我无法获得“ĝusti”、“ĝustivin”、“ĝuspa”到正确排序。我需要这样的代码来对单词进行排序:["bonanmatenon","ĉuviparolasesperanton","ĝuspa","ĝusti","ĝustivin","miamasvin","pacon"]defalphabetize(phrases)alpha="abcĉdefgĝhĥijĵklmnoprsŝtuŭvz".split(//)phrases.sort_by{|phrase|alpha.index

随机推荐