草庐IT

leetcode 139.单词拆分

wyj不吃草 2023-04-20 原文

题目链接：leetcode 139

1.题目

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

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

2.示例

1）示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

2）示例 2：
输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意，你可以重复使用字典中的单词。

3）示例 3：
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

3.数据范围

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

4.分析

首先可以遍历s分析s[x,y]这段区间内是否可以匹配成功，在此基础上，如果s[0:x]可以被匹配，且s[x+1:y]可以被匹配，那么s[0:y]可以被匹配，最终的结果就是s[s.size()-1]是否可以被匹配

5.代码

class Solution {
public:
    bool flag[210][210],f[210];
    void pre(string s, vector<string>& wordDict){
        memset(flag,false,sizeof(flag));
        for(int i=0;i<wordDict.size();i++)
            for(int j=0;j+wordDict[i].size()-1<s.size();j++){
                int ff=0;
                for(int k=0;k<wordDict[i].size();k++)
                    if(wordDict[i][k]!=s[j+k])
                    {
                        ff=1;break;
                    } 
                if(ff==0) flag[j][j+wordDict[i].size()-1]=true;
            }
    }
    bool get_ans(string s, vector<string>& wordDict)
    {
        memset(f,false,sizeof(f));
        for(int i=0;i<s.size();i++)
            if(flag[0][i]==true) f[i]=true;
        for(int i=0;i<s.size();i++)
            if(f[i]==true)
                for(int j=i+1;j<s.size();j++)
                    if(flag[i+1][j]==true)
                        f[j]=true;
        return f[s.size()-1];
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        pre(s,wordDict);
        return get_ans(s,wordDict);
    }
};
单词leetcodespanclasstoken算法

有关leetcode 139.单词拆分的更多相关文章

  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

随机推荐