Skip to content

Double Sequence I

Description

Given an input string (s) and a pattern (p), 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). - Note: - s could be empty and contains only lowercase letters a-z. - p could be empty and contains only lowercase letters a-z, and characters like . or *.

https://leetcode.com/problems/regular-expression-matching/description/

Example I:

Input:
s = "aa"
p = "a" Output: false
Explanation: "a" does not match the entire string "aa".

Example II:

Input:
s = "aa"
p = "a"
Output: true
Explanation: '' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example III:

Input:
s = "ab"
p = "."
Output: true
Explanation: "." means "zero or more (*) of any character (.)".

Example IV:

Input:
s = "mississippi"
p = "misisp*."
Output: false

Questions

  • LeetCode - 10. Regular Expression Matching

Analysis

0 1 2 3 4 5 6
a b * c . d $
0 a T F F F F F F
1 b F T T F F F F
2 b F T F F F F F
3 c F T F T F F F
4 f F F F F T F F
5 d F F F F F T F
6 $ F F F F F F T

Transform Function

if(s.charAt(i - 1) == p.charAt(j - 1)) {
    dp[i][j] = dp[i - 1][j - 1];
}else if(p.charAt(j - 1) == '.') {
    dp[i][j] = dp[i - 1][j - 1];
}else if(p.charAt(j - 1) == '*') {
    dp[i][j] = dp[i][j - 2]; // empty 
    if(p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) { // repeat match
        dp[i][j] = dp[i][j] || dp[i - 1][j];
    }
}

Solution

class Solution {
    public boolean isMatch(String s, String p) {
        char[] c1 = s.toCharArray();
        char[] c2 = p.toCharArray();
        int m = c1.length, n = c2.length;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for(int i = 1; i <= n; i++) {
            if(c2[i - 1] == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(c1[i - 1] == c2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else if(c2[j - 1] == '.') dp[i][j] = dp[i - 1][j - 1];
                else if(c2[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if(c2[j - 2] == '.' || c2[j - 2] == c1[i - 1]) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }

        return dp[m][n];
    }
}