Regular Expression Matching
Total Accepted: 13504 Total
Submissions: 67886My Submissions
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
本题解法： 1 二维动规，状态集合 vector< vector<Pair> > , vector<Pair>为p[0,i] 匹配到s的区间集合。 2 p/s两个字符串双线性扫描 匹配
Word Break II
Given a string s and a dictionary of words dict, add spaces in s to 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, words, vs, tag, ans, cur, 0);
return ans;
}