LeetCode. 10. Regular Expression Matching

On this page

[Link] https://leetcode.com/problems/regular-expression-matching/

Dynamic programming

This problem uses only two pattern operators: . matches exactly one arbitrary character, and * matches zero or more copies of the immediately preceding atom. Thus, * is handled together with the atom directly before it; it does not stand alone or apply to an earlier part of the pattern. The problem guarantees that every pattern is valid, so every * has a preceding atom.

Let dp[i][j] mean that the first i characters of s match the first j characters of p. The result is dp[s.length()][p.length()]. The empty prefixes match, so dp[0][0] is true. An empty string can match a nonempty pattern only when its final atom-star pair is skipped: for each valid x* pair, dp[0][j] = dp[0][j - 2].

For a pattern character other than *, it must match the current input character (either the same literal character or .), and the preceding prefixes must already match: dp[i][j] = matches(s[i - 1], p[j - 1]) && dp[i - 1][j - 1].

For an x* pair, there are two possibilities. It can match zero copies of x, leaving dp[i][j - 2]; or it can consume one matching input character and keep the same pattern pair available for further copies, requiring matches(s[i - 1], p[j - 2]) && dp[i - 1][j].

The table takes O(|s||p|) time and O(|s||p|) space.

Java

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

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

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char patternChar = p.charAt(j - 1);
                if (patternChar == '*') {
                    char atom = p.charAt(j - 2);
                    dp[i][j] = dp[i][j - 2]
                            || (matches(s.charAt(i - 1), atom) && dp[i - 1][j]);
                } else {
                    dp[i][j] = matches(s.charAt(i - 1), patternChar)
                            && dp[i - 1][j - 1];
                }
            }
        }

        return dp[m][n];
    }

    private boolean matches(char input, char atom) {
        return atom == '.' || input == atom;
    }
}