• 刷题仓库地址
• 4. Median of Two Sorted Arrays
• 10. Regular Expression Matching
• 23. Merge k Sorted Lists
• 25. Reverse Nodes in k-Group
• 30. Substring with Concatenation of All Words
• 32. Longest Valid Parentheses
• 37. Sudoku Solver

---

Description

Implement regular expression matching with support for ‘.’ and ‘*’.

Example

'.' 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

Translation

实现正则表达式匹配，支持’.’和’*’

‘.’ 匹配任意一个字符。

‘*‘ 匹配0个或多个 ‘*‘ 前面的一个字符

Ideas

使用递归。整体思路是：如果当前字符匹配成功，最终结果是之后的字符是否匹配成功。

定义递归函数recursion(String s,String p,int sIndex,int pIndex)

1. 结束条件: sIndex >= s.length() || pIndex >= p.length()

   需要注意的是:

   当s匹配结束后，还要判断模式串后面是否有 ‘a*b*‘等字符。
   当p匹配结束后，当且仅当s也匹配结束时返回true。

2. 当 p.charAt(pIndex+1) != '*' 时，

   即 当前匹配的不是 ‘*’

   当 p.charAt(pIndex) == s.charAt(sIndex)|| p.charAt(pIndex) == '.'时

   返回 recursion(s,p,sIndex+1,pIndex+1)

   如果条件不成立，则返回 false。

3. 当 p.charAt(pIndex+1) != '*' 时，

   即当前匹配的是 ‘*’

   使用贪心策略，如果当前位置的字符匹配，保持 pIndex不动，不断移动sIndex，每移动一次sIndex，

   就判断一次 recursion(s,p,sIndex,pIndex+2)。如果 ‘*’后面的所有字符都匹配，

   可以直接返回true。

   如果当前位置的字符不匹配，即 ‘*’ 已经匹配了足够多的字符（也有可能一个字符都没有匹配），

   说明 ‘*’ 匹配结束，返回 recursion(s,p,sIndex,pIndex+2)。

4. 注意递归结束条件，注意边界问题

Note

注意测试数据:

""   "a*"
"ab"  "c*a*b*d*"
"a"  "c*.a*"
"abc"  ".*"

1.

Accept Code

public class RegularExpressionMatching {
    public boolean isMatch(String s, String p) {
        return recursion(s, p, 0, 0);
    }

    private boolean recursion(String s, String p, int sIndex, int pIndex) {
        if (pIndex >= p.length()) {
            return sIndex >= s.length();
        }
        //解决 s = ab ，p = a*b*c*d
        if (sIndex >= s.length()) {
            if (pIndex + 1 < p.length() && p.charAt(pIndex + 1) == '*') {
                return recursion(s, p, sIndex, pIndex + 2);
            } else {
                return false;
            }
        }
        //解决 s = aa,p =  a
        if (pIndex + 1 >= p.length()) {
            if (p.charAt(pIndex) == s.charAt(sIndex) || p.charAt(pIndex) == '.') {
                return sIndex + 1 == s.length();
            } else {
                return false;
            }
        }
        if ((pIndex + 1 < p.length()) && p.charAt(pIndex + 1) != '*') {
            if (s.charAt(sIndex) == p.charAt(pIndex) || (sIndex < s.length() && p.charAt(pIndex) == '.')) {
                return recursion(s, p, sIndex + 1, pIndex + 1);
            } else {
                return false;
            }
        } else {
            while ((sIndex < s.length() && s.charAt(sIndex) == p.charAt(pIndex)) || (sIndex < s.length() && p.charAt(pIndex) == '.')) {
                if (recursion(s, p, sIndex, pIndex + 2)) {
                    return true;
                }
                sIndex++;
            }
            return recursion(s, p, sIndex, pIndex + 2);

        }
    }

    public boolean isMatch2(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];
    }
}