LeetCode - Regular Expression Ma

最近刷LeetCode遇到关于正则匹配的编程题，在这里记录下解题思路。

Regular Expression Matching

Link

Regular Expression Matching - LeetCode

Description

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

Recursive Solution

Discusss

当模式中的第二个字符不是“*”时：

1. 如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
2. 如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。

而当模式中的第二个字符是“*”时：

1. 如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
2. 如果字符串第一个字符跟模式第一个字符匹配，可以有2种匹配方式：
   1. 模式后移2字符，相当于x*被忽略;
   2. 字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位;

Code

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s.equals("") && p.equals("")) return true;
        if (!s.equals("") && p.equals("")) return false;
        if (p.length() > 1 && p.charAt(1) == '*') {
            return isMatch(s, p.substring(2)) ||
                    (s.length() != 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0)) && isMatch(s.substring(1), p));
        }
        if (s.length() != 0 && p.length() != 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0)))
            return isMatch(s.substring(1), p.substring(1));
        return false;
    }
}

Dynamic Planning Solution

Discusss

1. If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2. If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3. If p.charAt(j) == '*': 
   here are two sub conditions:
       1   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
       2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
                      dp[i][j] = dp[i-1][j]    // in this case, a* counts as multiple a 
                   or dp[i][j] = dp[i][j-2]    // in this case, a* counts as empty

Code

public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        for (int i = 0; i < p.length(); i++)
            if (p.charAt(i) == '*' && dp[0][i-1]) dp[0][i+1] = true;
        for (int i = 0 ; i < s.length(); i++) {
            for (int j = 0; j < p.length(); 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 
                         dp[i+1][j+1] = (dp[i][j+1] || dp[i+1][j-1]);
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}

Wildcard Matching

Link

Wildcard Matching - LeetCode

Description

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", "c*a*b") ? false

Recursive Solution

Discuss

当模式中的第一个字符不是“*”时：

1. 如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
2. 如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。

而当模式中的第一个字符是“*”时：

1. 模式后移1字符，相当于*被忽略;
2. 字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位;

Code

@Deprecated
//(TimeLimitExceededException)
public class Solution {
    public boolean isMatch(String s, String p) {
        if (s.length() == 0 && p.length() == 0) return true;
        if (s.length() != 0 && p.length() == 0) return false;
        if (s.length() > 0 && (p.charAt(0) == '?' || s.charAt(0) == p.charAt(0))) return isMatch(s.substring(1), p.substring(1));
        if (p.charAt(0) == '*') return isMatch(s, p.substring(1)) || (s.length() > 0 && isMatch(s.substring(1), p));
        return false;
    }
}

Dynamic Planning Solution

Discuss

1. If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2. If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3. If p.charAt(j) == '*': 
   here are two sub conditions:
          dp[i][j] = dp[i-1][j]    // in this case, * counts as multiple 
       or dp[i][j] = dp[i][j-1]    // in this case, * counts as empty

Code

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