单词拆分

作者:Lew's Personal Blog 发布于:2019-12-26 15:49 Thursday 分类:Leetcode

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

示例1

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true

解释: 返回 true 

因为 "leetcode" 可以被拆分成 "leet code"。


测试源代码


#include <string>
#include <iostream>
#include <vector>
using namespace std;
bool wordBreak(string& s, vector<string>& wordDict) 
{
    vector<int> dp(s.size() + 1, 0);
    dp[0] = 1;
for (int i = 0; i <= s.size(); ++i)
{
for (auto word : wordDict)//进行遍历
{
int ws = word.size();
if (i - ws >= 0)
{
int cur = s.compare(i - ws, ws, word);//掉用compare函数
if (cur == 0 && dp[i - ws] == 1)
{
dp[i] = 1;
}
}
}
}
return dp[s.size()];
}
int main(int argc, char **argv)
{
string s = "leetcofe";
cout << "the length of s: " << s.size() << endl;
vector<string> wordDict = { "leet", "code" }; //字符串数组
     cout << wordBreak(s, wordDict) << endl;
return 0;
}



标签: C++

  • 0
    掌声
  • 0
    感动
  • 0
    震惊
  • 0
    鄙视
  • 0
    无语

« 上一篇 队列 | leetcode测试代码 下一篇»

发表评论 »本文目前尚无任何评论

发表评论

干净网络从你做起,切勿黏贴小广告