给定一个非空字符串 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
想了好久如何ac自动机，后来还是觉得没法用，还是暴力好了。
unordered_map 查找插入复杂度都是O(1)
非常优秀。
dp[i]表示从0~i-1位都已经匹配好了，从i开始的未知。
ac代码：
class Solution {
public:
string tmp;
unordered_map<string,int> mp;
int dp[100010];
int len;
bool wordBreak(string s, vector<string>& wordDict) {
for(auto i : wordDict){
mp[i] = 1;
}
len = s.length();
dp[0] = 1;
for(int i = 0 ; i < len ; i++){
for(int j = 0 ; j <= i ;j++){
if(dp[j] ==0) continue;
tmp.clear();
tmp = s.substr(j,i-j+1);
auto f = mp.find(tmp);
if(f != mp.end()){//cout <<" i= "<<i<<endl;
dp[i+1] = 1;
}
}
}
if(dp[len]) return true;
else return false;
}
};
全部代码：
#include <bits/stdc++.h>
using namespace std;
vector<string> wordDict;
string s;
string tmp;
vector<string>ans;
unordered_map<string,int> mp;
int dp[100010];
int len;
bool sov(){
for(auto i : wordDict){
mp[i] = 1;
}
len = s.length();
dp[0] = 1;
for(int i = 0 ; i < len ; i++){
for(int j = 0 ; j <= i ;j++){
if(dp[j] ==0) continue;
tmp.clear();
tmp = s.substr(j,i-j+1);
auto f = mp.find(tmp);
if(f != mp.end()){//cout <<" i= "<<i<<endl;
dp[i+1] = 1;
}
}
}
if(dp[len]) return true;
else return false;
}
void init(){
int n;
string k;
scanf("%d",&n);
for(int i = 1; i <= n ; i++){
cin >> k;
wordDict.push_back(k);
}
cin >> s;
}
int main(){
// string r = "aspoefj";
// string tmp ="";
// tmp = r.substr(0,3);
// cout <<"tmp = "<<tmp<<endl;
init();
if(sov()) printf("true");
else printf("false");
}
/*
2
apple
pen
applepen
*/
