野球拳刷刷刷: 10. 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", "c*a*b") → true

Solution:

Method 1: DP

We use dynamic programming to determine whether s and p are match.

boolean match[i][j]: whether the first i characters in s match the first j characters in p.

There are two cases to consider:

1. s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j) == '.'.

match[i - 1][j - 1]

2. p.charAt(j) == '*'

a). match[i][j - 2], 0 occurrence of p.charAt(j - 1)
or
b). match[i - 1][j], if s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.'.

The time complexity is O(mn) and the space complexity is O(mn) as well.

Code:

public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
        match[0][0] = true;
        
        // deal with a*, a*b*, a*b*c*...
        for (int i = 1; i < match[0].length; i++) {
            if (p.charAt(i - 1) == '*') {
                match[0][i] = match[0][i - 2];
            }
        }
        for (int i = 1; i < match.length; i++) {
            for (int j = 1; j < match[0].length; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    match[i][j] = match[i - 1][j - 1];
                }
                else if (p.charAt(j - 1) == '*') {
                    
                    // s: x   p xa*, we check a* is empty, which is match[i][j - 2];
                    match[i][j] = match[i][j - 2];
                    
                    // s: xa  p: xa* -> a is part of a*, so we check s: x  p: xa*, which is match[i - 1][j]
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        match[i][j] = match[i][j] || match[i - 1][j];
                    }
                }
                else {
                    match[i][j] = false;
                }
            }
        }
        return match[s.length()][p.length()];
    }
}

Method 2: Optimization (Rolling Array)

We need to update match[i % 2][0] in the j loop.

Code:

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] match = new boolean[2][n + 1];
        match[0][0] = true;
        
        // p: a*, a*b*, a*b*c*...
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                match[0][j] = match[0][j - 2];
            }
        }
        
        for (int i = 1; i <= m; i++) {
            match[i % 2][0] = false;
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    match[i % 2][j] = match[(i - 1) % 2][j - 1];
                }
                else if (p.charAt(j - 1) == '*') {
                    // s: x  p: xa*
                    match[i % 2][j] = match[i % 2][j - 2];
                    
                    // s: xa  p: xa*  p: x.*
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        match[i % 2][j] = match[i % 2][j] || match[(i - 1) % 2][j];
                    }
                }
                else {
                    match[i % 2][j] = false;
                }
                
            }
        }
        
        return match[m % 2][n];
    }
}

Monday, June 5, 2017

10. Regular Expression Matching