[Leetcode] Regular Expression Matching 正则表达式匹配

Vixb 发布于2019-08-14 12:49 / 3467人阅读

摘要：为的条件是为，且第个字符也能被成功匹配。而从后往前匹配则不会影响该星号后面星号所匹配的部分，因为已经匹配的部分我们会直接跳过。这样才能防止最后字母没有匹配上，而前面的部分反而把的结尾给匹配了。

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

动态规划 复杂度

时间 O(NM) 空间 O(N)

思路

这道题可以用递归解决，不过时间复杂度是指数级，这里介绍一个用动态规划在平方时间内解决的办法。
解法的核心理念是：从后往前看pattern的每一位，对于pattern的每一位，我们尽可能的把待匹配串string从后往前给匹配上。我们用一个数组match[string.length() + 1]来表示string被匹配的情况，这里如果match[j]是true，而我们pattern正指向第i位，则说明string从第j位到最后都已经被pattern第i位之前的某些部分给成功匹配了，所以我们不用再操心了。match[i]为true的条件是match[i + 1]为true，且string第i个字符也能被成功匹配。

那我们就可以从后往前开始看pattern的每一位能匹配多少string的字符了：

如果pattern的这一位是*，那我们要用这一位，来从后往前尝试匹配string，因为string后面是已经匹配好的，前面是还没匹配好的，所以从前往后匹配星号可能会导致我们匹配了一些pattern该星号前面的星号应该匹配的部分。而从后往前匹配则不会影响pattern该星号后面星号所匹配的部分，因为已经匹配的部分我们会直接跳过。

如果pattern这一位不是*，那我们则不能匹配多个字符，我们只能匹配一个字符，这时候要对string从前往后匹配，因为如果后面没被匹配，前面也肯定不会被匹配，所以从前向后能保证我们把pattern的这一位匹配到string当前最后面那个还没匹配的字符。这样如果那个字符能被匹配就通过了。

我们举个例子

match:   0 0 0 1
string:  a a b
pattern: a * b
             |

这里我们先看pattern最后一位b能匹配到多少，这里因为b不是星号，所以我们从左往右尝试匹配string，第一个a不行，第二个a也不行，然后到b，这里因为match[3]是true，b也和b相同，所以匹配成功。

match:   0 0 1 1
string:  a a b
pattern: a * b
           |

然后看pattern的这个星号，我们要从后往前匹配string。因为b已经被匹配了，match[2]是true，所以直接跳过。然后到a，发现个pattern中星号前面的字符a相同，所以匹配成功，match[1]也置为true再看string的第一个a，还是可以匹配成功，这样整个string都被匹配成功了。

这里还有几个情况，首先，无论刚才那pattern中最后一个b有没有匹配到string中任何一个字符，match[3]也要置为false。这样才能防止pattern最后字母没有匹配上，而pattern前面的部分反而把string的结尾给匹配了。还有如果pattern中是句号的话，那相当于字符相同。

代码

public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[] match = new boolean[s.length() + 1];
        match[s.length()] = true;
        for(int i = p.length() - 1; i >=0; i--){
            if(p.charAt(i) == "*"){
                // 如果是星号，从后往前匹配
                for(int j = s.length() - 1; j >= 0; j--){
                    match[j] = match[j] || (match[j + 1] && (p.charAt(i - 1) == "." || (p.charAt(i - 1) == s.charAt(j)))); 
                }
                // 记得把i多减一，因为星号是和其前面的字符配合使用的
                i--;
            } else {
                // 如果不是星号，从前往后匹配
                for(int j = 0; j < s.length(); j++){
                    match[j] = match[j + 1] && (p.charAt(i) == "." || (p.charAt(i) == s.charAt(j)));
                }
                // 只要试过了pattern中最后一个字符，就要把match[s.length()]置为false
                match[s.length()] = false;
            }
        }
        return match[0];
    }
}

GPU云服务器云服务器正则匹配正则表达式正则表达式匹配匹配php正则表达式 regular_expression

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64725.html

Leetcode 10 Regular Expression Matching 简单正则匹配

摘要：难度这道题要求我们实现简单的正则表达式的匹配只要求普通字符的匹配了解正则的同学都清楚代表任意单个字符代表个或多个前面的字符比如可以匹配到空字符串也可以匹配等等题目还要求我们判定正则是否匹配给定的字符串要判定整个字符串而不是其中一部分匹配就算 Implement regular expression matching with support for . and *. . Matche...

OnlyLing 2019-08-14 17:14 评论0 收藏0
手动实现.*正则表达式匹配函数

摘要：手动实现正则表达式匹配函数思路使用迭代，当每次判断后令当时特殊处理，注意可以代表到多个之前一个的字符当时，循环判断代表多少个之前一个的字符，如果可以匹配之后的模式，返回，否则注意处理边界值的情况，和为空串时代码可以代表一到多次本题以及其它题手动实现.*正则表达式匹配函数 regular expression matching . Matches any single charact...

muddyway 2019-07-25 12:02 评论0 收藏0
[LeetCode] 10. Regular Expression Matching

Problem Given an input string (s) and a pattern (p), implement regular expression matching with support for . and *. . Matches any single character. * Matches zero or more of the preceding element. Th...

mo0n1andin 2019-08-16 13:28 评论0 收藏0
Python中fnmatch模块的使用

摘要：函数匹配能力介于简单的字符串方法和强大的正则表达式之间，如果在数据处理操作中只需要简单的通配符就能完成的时候，这通常是一个比较合理的方案。此模块的主要作用是文件名称的匹配，并且匹配的模式使用的风格。 fnmatch()函数匹配能力介于简单的字符串方法和强大的正则表达式之间，如果在数据处理操作中只需要简单的通配符就能完成的时候，这通常是一个比较合理的方案。此模块的主要作用是文件名称的匹配...

PAMPANG 2019-06-26 18:39 评论0 收藏0