Regular Expression Matching

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", "ca*b") → true

难度：hard

问题的关键是a和*一起match了0或者n个a。

Solution: Dynamic Programming

这个解法的关键是确定：在match当前元素的时候，*的pattern是第几次使用。

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }

        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for (int j = 0; j < n; ++j) {
            if (p.charAt(j) == '*' && dp[0][j - 1]) {
                dp[0][j + 1] = true;
            }
        }

        for (int i = 0 ; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (p.charAt(j) == '.') {
                    dp[i + 1][j + 1] = dp[i][j];
                }
                if (p.charAt(j) == s.charAt(i)) {
                    dp[i+1][j+1] = dp[i][j];
                }
                if (p.charAt(j) == '*') {
                    if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {
                        dp[i + 1][j + 1] = dp[i + 1][j - 1];
                    } else {
                        // 0 || 1 || n
                        dp[i + 1][j + 1] = (dp[i + 1][j - 1] || dp[i + 1][j] || dp[i][j + 1]);
                    }
                }
            }
        }
        return dp[m][n];
    }
}

Solution: Recursive

class Solution {
    public boolean isMatch(String s, String p) {
        return isMatch(s, 0, p, 0);
    }
    private boolean isMatch(String s, int i, String p, int j) {
        if(i == s.length() && j == p.length()) {
            return true;
        } else if(i != s.length() && j == p.length()) {
            return false;
        } else if(i == s.length() && j != p.length()) {
            if(j + 1 < p.length() && p.charAt(j + 1) == '*') {
                return isMatch(s, i, p, j + 2);
            } else {
                return false;
            }
        }

        if(p.charAt(j) == '.' || s.charAt(i) == p.charAt(j)) {
            if(j + 1 < p.length() && p.charAt(j + 1) == '*') {
                return isMatch(s, i + 1, p, j) || isMatch(s, i, p, j + 2);
            } else {
                return isMatch(s, i + 1, p, j + 1);
            }
        } else {
            if(j + 1 < p.length() && p.charAt(j + 1) == '*') {
                return isMatch(s, i, p, j + 2);
            }
        }
        return false;
    }
}

Wildcard Matching

Implement wildcard pattern matching with support for '?' and ''. '?' Matches any single character. '' Matches any sequence of characters (including the empty sequence). 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", "") → true isMatch("aa", "a") → true isMatch("ab", "?") → true isMatch("aab", "ca*b") → false

难度：hard

Solution: Dynamic Programming

问题的另一个关键是先要考虑s是空字符串时候的base case。

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for(int j = 0; j < n; ++j) {
            if(p.charAt(j) == '*') {
                dp[0][j + 1] = dp[0][j];
            }
        }
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(p.charAt(j) == '*') {
                    dp[i + 1][j + 1] = dp[i + 1][j] || dp[i][j] || dp[i][j + 1];
                } else if(p.charAt(j) == '?') {
                    dp[i + 1][j + 1] = dp[i][j];
                } else {
                    if(p.charAt(j) == s.charAt(i)) {
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}