GeezerVison is showing github.com — CodingInterview/Solution19.java at master · legolas007/CodingInterview

Expand file tree

Solution19.java

Copy path

More file actions

37 lines (35 loc) · 1.37 KB

Copy path

37 lines (35 loc) · 1.37 KB

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

package com.usher.algorithm.offer;

/**

* @Author: Usher

* @Description:

* if p.charAt(j) == s.charAt(i) : then dp[i][j] = dp[i-1][j-1];

if p.charAt(j) == '.' : then dp[i][j] = dp[i-1][j-1];

if p.charAt(j) == '*' :

if p.charAt(j-1) != s.charAt(i) : then dp[i][j] = dp[i][j-2] // a* only counts as empty

if p.charAt(j-1) == s.charAt(i)

or p.charAt(i-1) == '.' :

then dp[i][j] = dp[i-1][j] // a* counts as multiple a

or dp[i][j] = dp[i][j-1] // a* counts as single a

or dp[i][j] = dp[i][j-2] // a* counts as empty

public class Solution19 {

public boolean match(char[] str, char[] pattern) {

int m = str.length, n = pattern.length;

boolean[][] dp = new boolean[m + 1][n + 1];

dp[0][0] = true;

for (int i = 1; i <= n; i++)

if (pattern[i - 1] == '*')

dp[0][i] = dp[0][i - 2];

for (int i = 1; i <= m; i++)

for (int j = 1; j <= n; j++)

if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')

dp[i][j] = dp[i - 1][j - 1];

else if (pattern[j - 1] == '*')

if (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.')

dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j];

else

dp[i][j] = dp[i][j - 2];

return dp[m][n];

}