Regular Expression Matching
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
Hide Tags
Dynamic Programming Backtracking String
Hide Similar Problems
虽然看了网上帖子的讲解，但总觉得应该直接写一个迭代的会更快，加上之前做的 044 - Wildcard Matching 印象深刻，
所以总是想用 044 的套路，但怎么加条件都不能解决所有的 case，最后有十来个 test case 就是过不去。
仔细分析了一下判定的过程，情况跟 044 实际上并不一样：
044 的星号可以代表任何串，一旦出现新的星号，之前的星号就可以不再理会了，
所以只要记住最近的星号出现时 s/p 的位置就可以往回倒；
但这里的星号只能是多次重复星号前的字母，也就是说，并不是啥都能匹配，有时候倒回去到上一个却并不匹配，
如果只用两个下标记录之前匹配的而跳过不匹配的，向前遇到多组匹配的又会导致倒回到更早的位置上而产生错误的匹配。
而帖子中的代码是递归的，实际上调用栈就起到了缓存所有匹配位置的作用，
这些位置或是匹配，或是不匹配，但是都能通过调用栈逐步倒回去，所以就算要写迭代的解法，也必须借用一个栈。
放弃了 044 的单组下标就快了，先把所有“字母 + 星号”的组合视为出现 0 次，将其对应的 s/p 的下标都放到栈里，
如果单个字符匹配则继续往前移动，如果不匹配就要看栈里是否有东西了，
有的话就意味着可以尝试回头让“字母 + 星号”的组合出现一次来多吃掉一个字符，否则就说明没法继续了，返回失败。
倒回去的时候，如果从栈里取出来的组合不匹配，就继续取，直到遇到匹配的（继续前进），或者栈取空了（返回失败）。
如此循环往复，最终如果能同时走到 s 和 p 的终点，那么就意味着完成了匹配，返回成功。
比较讶异的是，用 STL 的栈做出来的性能相当一般，344 ms。
试着把帖子里的递归算法自己写了一遍，24 ms！1/14 的耗时！
STL 栈迭代的执行过程跟递归逻辑上是一样的，单字匹配推进，星号前缀匹配先忽略而后回溯吃字符再继续，不匹配跳过，
可见模板是有相当代价的。。。（回头试试vector会不会好一点，或者一次性 push 进 vector 用下标移动？？）
看看还有性能更好的，想来必然是 DP 了 （可是 044 的 DP 结果相当惨…？当然，044 的 test case 有长度 4090 的字符串…）。
比划了一番，应该就是一个地方要注意，就是对于星号：
如果其前缀跟当前 s[y-1] 匹配，它是取 左边，左上，以及 上上(星号可以让前缀出现 0 次) 方的三个值求或；
其中左边表示利用星号让其前缀字符重复；上上代表利用星号让其前缀出现零次；左上则表示之前匹配的结果。
【补】经过仔细的分析，实际上，左上是不需要的，原因是：
如果左上是 true，那么它的前缀与 s[y-2] 也就匹配上了，因此它左上的下面，也就是星号左边，也必然是true，
因此只要看左边和上上方就足够了。这实际上也符合星号的定义：其前缀字母可以出现任意次。
如果不匹配，就直接继承 上上 方的值就好了（在它之前的匹配情况）。
至于单字匹配，当然就是直接继承左上的结果了，也就是之前的两个子串的匹配情况。
写完了一跑还真吓了一跳，4 ms 就搞定了！
NND 因为 044 的 DP 实在太惨烈，栈击穿之后改 2 个滚动数组还是惨不忍睹，没敢想 DP 啊。
class Solution {
public:
//---------------------------------- STL Stack ----------------------------------
bool isMatch_stack(string s, string p)
{
int slen=s.length(), plen=p.length(), sidx=0, pidx=0;
bool backing=false;
stack<pair<int, int>> buf;
while(pidx<=plen)
{
if(sidx==slen && pidx==plen)
return true;
//if there is a "_*" pattern
if(pidx<plen-1 && '*'==p[pidx+1])
{
//backtracking
if(backing)
{
//if matches
if(sidx<slen && (s[sidx]==p[pidx] || '.'==p[pidx]))
{
sidx++;
buf.push({sidx, pidx});
pidx += 2;
backing = false;
}
//if not match, check next in stack until match or empty
else
{
if(buf.size())
{
sidx = (buf.top()).first;
pidx = (buf.top()).second;
buf.pop();
}
else
return false;
}
}
//if it's not backtracking, simply move forward either match or not
else
{
buf.push({sidx, pidx});
pidx += 2;
}
}
//no "_*" pattern
else
{
//if matches, move one character forward
if(sidx<slen && (s[sidx]==p[pidx] || '.'==p[pidx]))
sidx++, pidx++;
//if not, do backtracking
else
{
if(buf.size())
{
backing = true;
sidx = (buf.top()).first;
pidx = (buf.top()).second;
buf.pop();
}
else
return false;
}
}
}
return true;
}
//----------------------------------- Recursive -----------------------------------
bool isMatch_recursive(string s, string p){
return isMatching(s.data(), p.data());
}
bool isMatching(const char* s, const char* p)
{
if('\0'==*p)
return ('\0'==*s);
//there is a "_*" pattern
if('*'==*(p+1))
{
//if matches, go further as if ignoring them
//but will back here and "swallow" one more character and try again
//since there is a matching
while('\0'!=*s && (*s==*p || '.'==*p))
{
if(true==isMatching(s, p+2))
return true;
else
s++; //backtracking by "swallow" one more character
}
//if not match, simply treat them as non-occurrence and move on
return isMatching(s, p+2);
}
//if no "_*" pattern
else
{
//move on if single character matches
if('\0'!=*s && (*s==*p || '.'==*p))
return isMatching(s+1, p+1);
//otherwise failes here.
else
return false;
}
}
//----------------------------------- DP -----------------------------------
bool isMatch(string s, string p)
{
int slen=s.length(), plen=p.length();
bool buf[plen+1][slen+1];
for(int x=0; x<=plen; ++x)
{
//initialization for row head as if s is an empty string, buf[0][0] is true(match)
//if p[x-1] is *, take previous of previous value since _* can be empty
buf[x][0] = (!x) ? true : (('*'==p[x-1])?buf[x-2][0]:false);
for(int y=1; y<=slen; ++y)
{
if(!x)
buf[0][y] = false; //initialization as if p is an empty string
else
{
if('*'==p[x-1])
{
//prefix of * matches s[y], check up_up and left. (no need to check up_left)
if('.'==p[x-2] || p[x-2]==s[y-1])
buf[x][y] = (buf[x-2][y] || buf[x][y-1]); //no need to check buf[x-1][y-1]
//prefix of * doesn't match s[y], just take the value of up_up
else
buf[x][y] = buf[x-2][y];
}
else
{
//if p[x-1] and s[y-1] match, take value of up_left (previous string match result)
if('.'==p[x-1] || p[x-1]==s[y-1])
buf[x][y] = buf[x-1][y-1];
//if p[x-1] and s[y-1] don't match, it's false
else
buf[x][y] = false;
}
}
}
}
return buf[plen][slen];
}
};
344 ms, 24 ms, 4 ms.
【再补】
到讨论区看了一眼，还有玩得更精炼的，只用了一维数组就搞定的 DP：
他的想法是只看单个字符的匹配情况，至于星号，根据其前缀来判断是否置为 true
（指针 p 一直在增加，所以总是用 p[0] 表示前缀，p[1] 表示星号）
置了 true 的星号又会影响其后的单个字符，这样就把匹配的关系传递下去了，甚为巧妙！bool isMatch(char* s, char* p) {
const int SLEN = strlen(s);
bool matchs[SLEN+1];
memset(matchs, 0, sizeof(matchs));
matchs[0] = true;
while(p[0] != '\0'){
if('*' == p[1]){
for(int i = 0; i <= SLEN; ++i)
if(!matchs[i] && i!=0 && matchs[i-1] && ('.' == p[0] || p[0] == s[i-1]))
matchs[i] = true;
p = p + 2;
}
else{
for(int i = SLEN; i >=0; --i)
if(i!=0 && matchs[i-1] && ('.' == p[0] || p[0] == s[i-1]))
matchs[i] = true;
else
matchs[i] = false;
++p;
}
}
return matchs[SLEN];
}
No comments:
Post a Comment