LeetCode #10 Regular Expression Matching (H)

[Problem]

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

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

[Analysis]

这题我的思路是recursive的backtracking。先将问题转化为s[i...end]及p[j...end]的matching问题，然后对j分两种情况讨论：

1. j + 1 < p.length() && p[j + 1] == ‘*‘:

当s[i]与p[j]可以配对, 尝试配对s[i...end]及p[j+2...end]，直到s[i]与p[j]不对应则返回match(s, i, p, j+2)

2. else:

假如s[i]可以与p[j]配对，则返回match(s, i+1, p, j+1)

做到这样已经可以通过OJ了。进一步利用Dynamic Programming的思路储存中间结果，可以优化时间。

[Solution]

public class Solution {
    public boolean isMatch(String s, String p) {                 
        return match(s, 0, p, 0);
    }

    public boolean match(String s, int i, String p, int j) {
        if (j == p.length()) {
            return i == s.length();
        }
        
        if (j + 1 < p.length() && p.charAt(j + 1) == ‘*‘) {
            while (i != s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == ‘.‘)) {
                if (match(s, i, p, j + 2)) {
                    return true;
                }
                i++;                
            }
            
            return match(s, i, p, j + 2);
        } else {
            if (i != s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == ‘.‘)) {
                return match(s, i + 1, p, j + 1);
            }
        }
        
        return false;
    }
}

LeetCode #10 Regular Expression Matching (H)

原文：http://www.cnblogs.com/zhangqieyi/p/4856620.html