10. Regular Expression Matching


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)。

  1. 注意递归结束条件,注意边界问题

Note

注意测试数据:

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

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];
    }
}

版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
本文链接:https://zdran.com/20180328.html