【LeetCode】No.10. Regular Expression Matching -- Java Version

题目链接： https://leetcode.com/problems/regular-expression-matching/

Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:

【Translate】： 给定一个输入字符串s和一个模式p，实现支持’.‘和’*'的正则表达式匹配

• ‘.’ Matches any single character.​​​​
• ‘*’ Matches zero or more of the preceding element.

【Translate】：

• '.'匹配任何单个字符。
• '*'匹配前面元素的零个或多个。

The matching should cover the entire input string (not partial).

【Translate】： 匹配应该覆盖整个输入字符串(而不是部分)。

测试用例：



约束：

  一开始想的确实是太简单了，没有考虑过s比p小的情况。只是简单的设置了两种s.length()>=p.length()情况下的两种正确可能。而这一题的难点就在“包含”，即在p中能找到一子串与s相匹配。

    public boolean isMatch1(String s, String p) {
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
        if(p.equals(".*"))
        {
            return true;
        }
        
        for(int i = 0; i< s.length(); i++){
            
            if(p.length()>=2 && cs[i] == cp[0] && cp[i+1] == '*' )
            {
                return true;
            }
            if(i < p.length() && (cp[i] == '.'||cp[i] == cs[i]) && s.length() == p.length())
            {
                return true;
            }
        }
        
        return false;
    }

  Solution中的Approach 1，一层一层剥皮，去判断。

• 如果没有星号(正则表达式的*通配符)，问题就会更简单—我们只需从左到右检查文本中的每个字符是否与模式匹配。
• 当出现星号时，我们可能需要检查文本的许多不同后缀，看看它们是否与模式的其他部分匹配。递归解决方案是表示这种关系的一种直接方法。

    public boolean isMatch(String text, String pattern) {
        if (pattern.isEmpty()) return text.isEmpty();
        boolean first_match = (!text.isEmpty() &&
                               (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

        if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
            return (isMatch(text, pattern.substring(2)) ||
                    (first_match && isMatch(text.substring(1), pattern)));
        } else {
        	// ⇒ text - 1 ; pattern - 1
            return first_match && isMatch(text.substring(1), pattern.substring(1));
        }
    }

  matches() 方法用于检测字符串是否匹配给定的正则表达式，直接调用，一步到位。

    public boolean isMatch(String s, String p) {
        return s.matches(p);
    }

     public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        for (int j = 1; j<=p.length(); j++){
            if(p.charAt(j-1) == '*' && dp[0][j-2]){
                dp[0][j] = true;
            }
        }
        for (int i = 1; i<=s.length(); i++){
            for (int j = 1; j<=p.length(); j++){
                if(p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(p.charAt(j-1) == '*'){
                    if(p.charAt(j-2) != s.charAt(i-1) && p.charAt(j-2)!='.'){
                        dp[i][j] = dp[i][j-2];
                    }
                    else{
                        dp[i][j] = (dp[i][j-2] || dp[i][j-1] || dp[i-1][j]);
                    }
                }
            }
        }
        return dp[s.length()][p.length()];

    }

[1] Easy DP Java Solution with detailed Explanation
[2] Java substring() 方法
[3] Java matches() 方法
[4] Java Stack 类