Implement regular expression matching with support for'.'and'*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s,const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa","a*") → true
isMatch("aa",".*") → true
isMatch("ab",".*") → true
isMatch("aab","c*a*b") → true
@H_404_29@本题解法： 1 二维动规，状态集合 vector< vector<Pair> >,vector<Pair>为p[0,i] 匹配到s的区间集合。 2p/s两个字符串双线性扫描 匹配
Word Break II
Given a stringsand a dictionary of wordsdict,add spaces insto construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example,given
s="catsanddog",
dict=["cat","cats","and","sand","dog"].
A solution is["cats and dog","cat sand dog"].
一维动规， 但是注意需要加一个预处理（处理方法为WORD Break I）。。。
关键点：
预处理： tag【i】记录 【i,n-1】能否被成功划分，从而提前剪枝。
不要一开始就计算每个状态的解集，因为大部分状态都没用，而计算起来超级费时间和空间。 从这个角度，为了节省时间除了剪枝，还有记忆化搜索也可以。
代码
void kmp(string &s,string &p,vector<int> &pos){
if(p.length()<1) return;
int n = p.length();
vector<int> pre(n+1,-1);
pre[1] = 0;
for(int i=1; i<n; i++){
int t = pre[i];
while(t>=0 && p[t]!=p[i]){
t = pre[t];
}
pre[i+1] = t+1;
}
int m = s.length();
for(int i =0,j=0; i<=m; i++,j++){//@error: not i< m
if(j == n) {
pos.push_back(i-n);
}
while(j>=0 && p[j]!=s[i]){//@error: not s[j]!=p[i]
j = pre[j];
}
}
}
void dfs(const string &s,const vector<string> &words,const vector<vector<pair<int,int> > > &vs,const vector<bool> &tag,vector<string> &res,vector<int> &cur,int idx){
if(idx >= (int)s.length()){
string tmp = "";
for(int j = 0; j<cur.size(); j++){
tmp+=words[cur[j]];
if(j<cur.size()-1) tmp+=" ";
}
//cout<<tmp<<endl;
res.push_back(tmp);
return;
}
for(int i = 0; i<vs[idx].size(); i++){
const pair<int,int> & p = vs[idx][i];
if(!tag[p.first+1]) continue;// p.first+1 ~ n-1 not valid
const int num = p.second;
cur.push_back(num);
dfs(s,words,vs,tag,res,cur,p.first+1);//@error: not p.first+1
cur.pop_back();
}
}
vector<string> wordBreak(string s,unordered_set<string> &dict) {
int n = s.length();
vector<vector<pair<int,int> > > vs(n);
vector<bool> tag(n+1,false);
tag[n] = true;
vector<string> words;
for(unordered_set<string>::iterator it = dict.begin(); it!=dict.end(); it++){
words.push_back(*it);
}
for(int i =0; i<words.size(); i++){
vector<int> tmp;
kmp(s,words[i],tmp);
int l = words[i].length();
for(int j = 0; j<tmp.size(); j++){
int k = tmp[j];
vs[k].push_back(pair<int,int>(k+l-1,i));
//cout<<k<<","<<k+l-1<<":"<<i<<endl;
}
}
for(int i = n-1; i>=0; i--){
for(int j = 0; j<vs[i].size(); j++){
int k = vs[i][j].first;
// i ~ k
if(tag[k+1]) { tag[i] = true; break;}
}
}
vector<string> ans;
vector<int> cur;
dfs(s,ans,0);
return ans;
}
