85单词拆分(139)

作者: Turbo时间限制: 1S章节: 动态规划

晚于: 2020-09-02 12:00:00后提交分数乘系数50%

截止日期: 2020-09-09 12:00:00

问题描述 :

给定一个非空字符串 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

输入说明 :

第一行输入字符串s

第二行输入字典 wordDict中单词的数目n

第三行输入n个字符串，以空格分隔

输出说明 :

输出true或false

输入范例 :

catsandog 5 cats dog sand and cat

输出范例 :

false

#include <iostream>
#include <vector>
#include <string> 
#include <unordered_set>
using namespace std;
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) 
    {
        vector<bool> dp(s.size()+1,false);//dp[i]表示s的前i个字符能否被拆分
        unordered_set<string> ma(wordDict.begin(),wordDict.end());
        dp[0]=true;
        for(int i=1;i<=s.size();i++)
        {
            for(int j=0;j<i;j++)
            {
                if(dp[j]&&ma.find(s.substr(j,i-j))!=ma.end())
                {
                    dp[i]=true;
                    break;
                }
            }
        }
    return dp[s.size()];
    }
};
int main()
{
    string s,str;
    vector<string> words;
    int n;
    cin>>s;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>str;
        words.push_back(str);
    }
    bool res=Solution().wordBreak(s,words);
    if (res)
        cout<<"true";
    else
        cout<<"false";

    return 0;
}