10. Regular expression matching

First definition:

  • Let s be the original string and p be the matching string

  • Dp [I] [j] indicates whether the characters 1 through I of the s string match the characters 1 through J of the p string

So we come back to the definition:

If s = = p [j] [I] | | p [j] = = ‘. ‘, then clearly dp [I + 1] [j + 1) = dp [I] [j];

If p[j]==’*’ then we consider the following three cases

  1. Dp [I +1] [j+1] = dp[I +1] [J]
  2. Dp [I +1] [j] = dp[I +1] [j]
  3. Match at this time * said more, you must meet to match a situation: [I] = s = p [1] | | p [1] = = ‘. ‘
    • Dp [I] [j+1] = dp[I] [j+1]

But there are also initial conditions to consider:

Clearly by definition dp[0] [0] =true

Because dp[1~k] [0] cannot be true, there is no need to initialize it again

And dp [0] [1] ~ k is possible is true, then need to initialize, if p [j] = = ‘*’ so dp [0] [j + 1) = dp [0] [1]

The code is as follows:

    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) == The '*' && j > 0) dp[0][j+1] = dp[0][j - -1];
        }
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                if (p.charAt(j) == '. ' || p.charAt(j) == s.charAt(i)) {
                    dp[i + 1][j + 1] = dp[i][j];
                } else if (p.charAt(j) == The '*') {
                    if (j > 0) dp[i + 1][j + 1] |= dp[i + 1][j - 1];
                    dp[i + 1][j + 1] |= dp[i + 1][j];
                    if (j > 0 && (p.charAt(j - 1) = ='. ' || p.charAt(j - 1) == s.charAt(i)))
                        dp[i + 1][j + 1] |= dp[i][j+1]; }}}return dp[s.length()][p.length()];
    }
Copy the code