美文网首页
算法-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.正则表达式匹配

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