政子的博客

技术|学习|随笔

CodingInterview-正则表达式匹配

这道题在 Leetcode 中见过，大概思路是分两条线，一条是匹配 nowStr 和 nowPattern 的关系，一条是 nextPattern 是否是*。

  1. 如果 nowPattern 是 . 且 nowStr 没到结尾，或者 nowStr 和 nowPattern 相等，且 nextPattern 不是*，这是最简单的一个匹配，可以就直接匹配下一个（posStr+1，posPattern+1）。
  2. 如果 nowPattern 是 . 且 nowStr 没到结尾，或者 nowStr 和 nowPattern 相等，且 nextPattern 是*，那么就有两种考虑，要么跳过 nowStr，匹配 posStr+1（*匹配成功了一回），要么跳过 nowPattern，匹配 posPattern+2（*没有匹配成功）。
  3. 如果 nowPattern 不是. ， nowStr 和 nowPattern 不等，且 nextPattern 不是*，那么就匹配失败，返回 false。
  4. 如果 nowPattern 不是. ， nowStr 和 nowPattern 不等，且 nextPattern 是*，那还有救，可能是 nowPattern 被匹配了 0 次，可以直接跳过 nowPattern，匹配 posPattern+2。

做题的时候还需要注意：

  1. 不要把\0 写成了\n。
  2. 记得在测试 nowPattern 是 . 的时候还要测试 nowStr 没有到结尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool match(char* str, char* pattern)
    {
        if(str==NULL || pattern==NULL) return false;
        return match(str,pattern,0,0);
    }
    bool match(char* str,char* pattern,int posStr,int posPattern){
        char nowStr=str[posStr];
        char nowPattern=pattern[posPattern];
        if(nowStr=='\0' && nowPattern=='\0') return true;
        if(nowStr!='\0' && nowPattern=='\0') return false;
        char nextPattern=pattern[posPattern+1];
        if((nowPattern=='.' && nowStr!='\0') || nowStr==nowPattern){
            if(nextPattern=='*'){
                return match(str,pattern,posStr+1,posPattern)
                    || match(str,pattern,posStr,posPattern+2);
            }else{
                return match(str,pattern,posStr+1,posPattern+1);
            }
        }else{
            if(nextPattern=='*') return match(str,pattern,posStr,posPattern+2);
            else return false;
        }
    }
};