正则表达式匹配

C++，dp，递归，字符串匹配。

像这种题，最容易忘记，索性思路写的详细一点。

大体思路：使用从前往后“消除”的思路，使用双指针，对于指针之前的可以不管，只判断当前位置和以后的字符串的匹配情况，然后使用相同的策略进行递归匹配。

详细匹配步骤：

如果str和pattern指针都指向\0，则说明已经全部匹配成功了；
如果str和pattern指针指向的字符相等或者是pattern指向的是.，说明当前字符匹配成功：
1. 如果pattern的下一个字符是*，说明pattern可以重复前一个字符0次-n次：
  1. 如果是需要重复前一个字符0次，则说明消除上一个字符，则下次匹配应该从*的下一个字符开始，也就是改变递归参数：return match(str, pattern + 2);
  2. 如果是需要重复前一个字符1-n次，则下次匹配就应该直接从pattern指针指向字符开始就好，也就是递归return match(str + 1, pattern);
  3. 所以应该合并上述两种情况，也就是return match(str + 1, pattern) || match(str, pattern + 2);
2. 如果不是*，直接进行下一层匹配就好return match(str + 1, pattern + 1);
如果当前字符没有匹配成功：
1. 如果pattern的下一个字符是*，说明可以重复前一个字符0次，也就是把当前字符不匹配给消去，然后继续下一层匹配return match(str, pattern + 2);
2. 如果没有*，说明这里已经匹配失败了，返回false就好

代码如下：

class Solution {
public:
    bool match(char* str, char* pattern) {
        if (*str == '\0' && *pattern == '\0')
            return true;
        if (*str == *pattern || (*pattern == '.' && *str != '\0')) {
            if (*(pattern + 1) == '*')
                return match(str + 1, pattern) || match(str, pattern + 2);
            else
                return match(str + 1, pattern + 1);
        }
        else if (*(pattern + 1) == '*')
            return match(str, pattern + 2);
        return false;
    }
};

正则表达式匹配

你快乐吗？

正则表达式匹配

CATALOG

FEATURED TAGS

FRIENDS