LeetCode hot100系列——10. regular-expression-matching(动态规划、状态机)

RebornLee 2019-08-21

题目描述

https://leetcode-cn.com/probl...

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

输入示例:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

思路分析

双指针游走法(失败的方法)

自己最开始想到的方法,相当于是没有回溯的回溯法,导致s='aaa' p='a*a'这种情况匹配失败

暴力解法(官网答案叫做回溯法)

大体上就是通过递归的手段把匹配的问题抛给下一层

先从简单的想起,如果没有'.'和'*',那么字符串的匹配就是很简单的两个指针i和j,分别对着s和p,然后依次对比。
这时,考虑加上'.',对比字符s[i]和p[j]的时候,只需要把s[i]==p[j]加上p[j]=='.'的判断就可以
最后,再加上'*'的逻辑,根据对示例的观察,可以发现遇到*有这样几种情况(根据示例归纳出规律):

  1. aabc*a*b,这里c*并没有匹配成功a,所以c*的含义就是取0个c
    LeetCode hot100系列——10. regular-expression-matching(动态规划、状态机)
  2. 再看aaba*b,注意这里有两种情况
    1) aab的a算做匹配成功一个a,因此s的指针后移
    2) aab的a算做匹配成功0个a,这个是容易忽略掉的,这种时候p的指针后移两位
    LeetCode hot100系列——10. regular-expression-matching(动态规划、状态机)
    因此,如图,当s和p的元素相等的时候,其实是有两条判断路径的,因此这里需要使用递归来同时结合两种路径的结果来判断

完整的aab匹配c*a*b的过程如下图:
LeetCode hot100系列——10. regular-expression-matching(动态规划、状态机)
写出伪代码

if p[j+1]=='*' and s[i]==p[j]:
    j+2 recursive || i+1 recursive
if p[j+1]=='*' and s[i]!=p[j]:
    j+2 recursive
if p[j+1] != '*':
    if s[i]==p[j]:
        i+1 and j+1 recursive
    else:
        return false

递归出口,

  1. 没有*号了,两个单纯的字符比较失败,返回false
  2. s和p都遍历完了,返回true
  3. p没有*号了,s和p没有一起遍历完,返回false

动态规划

基于暴力解法,通过自顶向下的备忘录方式,或者自底向上的方式记录信息

根据pattern生成状态机

这种是标准的正则表达式的解决方式,通过解析请求的pattern,然后画出来一幅该正则式的有限状态机图,然后再对着图匹配字符串

代码实现

个人的错误解法

这个是个错误解法,aaaa*a的情况会由于指针没有回溯导致匹配失败,稍后分析

class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0, j = 0;
        while(i < s.length() && j < p.length()) {
            if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                if(j + 1 < p.length() && p.charAt(j+1) == '*') {
                    i++;
                } else {
                    i++;
                    j++;
                }
            } else if(j + 1 < p.length() && p.charAt(j+1) == '*') {
                j += 2;
            } else {
                return false;
            }
        }
        while(i == s.length() && j + 1 < p.length() && p.charAt(j+1) == '*') {
            j+=2;
        }
        if(i == s.length() && j == p.length()) {
            return true;
        } else {
            return false;
        }
    }
}

正确解法之回溯法

class Solution {
    public boolean isMatch(String s, String p) {
        return match(s, p, 0, s.length(), 0, p.length());
    }
    
    private boolean match(String s, String p, int sbegin, int send, int pbegin, int pend) {
        if(sbegin >= send && pbegin >= pend) {
            // exit
            return true;
        }
        if(pbegin + 1 < pend && p.charAt(pbegin + 1) == '*') {
            if(sbegin >= send) {
                // s is empty
                return match(s, p, sbegin, send, pbegin+2, pend);
            }
            if(s.charAt(sbegin) == p.charAt(pbegin) || p.charAt(pbegin) == '.') {
                return match(s, p, sbegin, send, pbegin+2, pend) || match(s, p, sbegin+1, send, pbegin, pend);
            } else {
                return match(s, p, sbegin, send, pbegin+2, pend);
            }
        } else {
            if(sbegin >= send || pbegin >= pend) {
                // exit
                return false;
            }
            if(s.charAt(sbegin) == p.charAt(pbegin) || p.charAt(pbegin) == '.') {
                return match(s, p, sbegin+1, send, pbegin+1, pend);
            } else {
                return false;
            }
        }
    }
}

个人总结

graph TD
A(分析例子) --> B(归纳出规律)
B --> C(画图)
C --> D(写伪代码确定递归推进和出口)

容易忘掉,例如aaa匹配a*a,匹配成功了a*也是可以当做匹配了0个的,此外注意指针直接推进是不行的,匹配完之后必须要判断后面的子串是否匹配成功(以此为依据才想到了递归)
不然容易出现a*直接把aaa都匹配完了,算作匹配失败

相关推荐

tuniumobile / 0评论 2018-12-26
陶赫Qt开发学习 / 0评论 2018-12-26