美文网首页
算法-19.正则表达式匹配

算法-19.正则表达式匹配

作者: zzq_nene | 来源:发表于2020-08-17 10:31 被阅读0次

请实现一个函数用来匹配包含'. '和''的正则表达式。模式中的字符'.'表示任意一个字符,而''表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式,即每个字符都在另一个字符串中能找到对应的匹配字符。例如,字符串"aaa"与模式"a.a"和"abaca"匹配,但与"aa.a"和"ab*a"均不匹配。

一、递归算法

    /**
     * 正则表达式匹配
     * @param s
     * @param p
     * @return
     * 举例:比如s="aaa",p="ab*ac*a"
     * 第一次调用isMatch的时候,第一个字符匹配,且p的第二个字符不是*,第二次是return true,所以本次也是return true
     * 第二次调用isMatch的时候,s="aa",p="b*ac*a",第一个字符不匹配,且p的第二个字符是*,第三次return true,所以本次也是return true
     * 第三次调用isMatch的时候,isMatch(s, p.substring(2)),s="aa",p="ac*a"
     * 此时第一个字符匹配,且p的第二个字符不是*,第四次是return true,所以本次也是return true
     * 第四次调用isMatch的时候,s="a",p="c*a",
     * 此时第一个字符不匹配,且p的第二个字符是*,因为第五次return true所以本次也是return true
     * 第五次调用isMatch的时候,isMatch(s, p.substring(2)),s="a",p="a"
     * 都只有一个字符,且匹配,所以return true
     */
    public static boolean isMatch(String s, String p) {
        if (p.length() <=0) return s.length() <= 0;
        // 判断第一个字符是否匹配
        boolean match = (s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'));
        // 如果第二个字符是*
        if (p.length() > 1 && p.charAt(1) == '*') {
            // isMatch(s, p.substring(2))如果第一个字符不匹配,那么验证从p的第三个字符开始的字符串与s是否匹配
            // 如果第一个字符匹配,那么从s的第二个字符开始判断与p是否匹配
            return isMatch(s, p.substring(2)) || (match && isMatch(s.substring(1), p));
        } else {
            // 如果第二个不是*,且第一个字符匹配,而分别从第二个字符开始继续匹配
            return match && isMatch(s.substring(1), p.substring(1));
        }
    }

二、动态规划

    private static boolean[][] memo;

    public static boolean isMatch1(String s, String p) {
        memo = new boolean[s.length() + 1][p.length() + 1];
        return match(0, 0, s, p);
    }

    public static boolean match(int i, int j, String text, String pattern) {
        if (memo[i][j]) {
            return memo[i][j];
        }
        boolean ans;
        if (j == pattern.length()){
            ans = i == text.length();
        } else{
            boolean curMatch = (i < text.length() &&
                    (pattern.charAt(j) == text.charAt(i) ||
                            pattern.charAt(j) == '.'));

            if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                ans = (match(i, j+2, text, pattern) ||
                        curMatch && match(i+1, j, text, pattern));
            } else {
                ans = curMatch && match(i+1, j+1, text, pattern);
            }
        }
        memo[i][j] = ans;
        return ans;
    }

这个算法比较难,转载自:
【LeetCode】正则表达式匹配(动态规划)

相关文章

  • 算法-19.正则表达式匹配

    请实现一个函数用来匹配包含'. '和''的正则表达式。模式中的字符'.'表示任意一个字符,而''表示它前面的字符可...

  • 正则表达式的匹配原理是什么

    正则表达式是如何实现查找匹配的? 1,正则表达式的使用2,正则表达式匹配搜索算法3,正则表达式引擎:DFA和NFA...

  • 算法:".*"正则表达式实现

    算法:".*"正则表达式实现 题目描述:请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示...

  • LeetCode-10-正则表达式匹配

    LeetCode-10-正则表达式匹配 题目说明 解法思路 1 该题的标签为回溯算法,所以采用回溯算法来解决此题,...

  • Nginx 匹配规则

    无 :默认匹配,普通匹配 = :精确匹配 ~* :匹配正则表达式,不区分大小写 ~ :匹配正则表达式,区分大小写 ...

  • 2019.8.15分享:正则表达式字符匹配攻略

    一、正则表达式 正则表达式是匹配模式,要么匹配字符,要么匹配位置。 这次分享主要将提下正则表达式字符匹配 • 两种...

  • python与正则表达式 2020-01-02(未经允许,禁止转

    正则表达式 正则表达式与程序语言无关。正则表达式做匹配实际上就做3件事:【字符匹配】+【次数匹配】+【逻辑匹配】下...

  • 《javaScript正则表达式迷你书》(一)

    正则表达式字符匹配攻略 正则表达式是匹配模式,要么匹配字符,要么匹配位置。 两种模糊匹配 如果正则只有精确匹配是没...

  • 正则加^$与不加的区别

    加^$的正则表达式,表示完整匹配。 正则表达式匹配内容匹配结果说明/bc/abcdefg成功包含就能匹配成功/^a...

  • 正则表达式收集

    常用正则表达式大全 常用正则表达式大全!(例如:匹配中文、匹配html) 匹配中文字符的正则表达式:[u4e00-...

网友评论

      本文标题:算法-19.正则表达式匹配

      本文链接:https://www.haomeiwen.com/subject/bwpfdktx.html