# The dumb AC code.

• I have spent a long time to figure this problem out. Here is my AC code in java, it's a little bit complex so I added a lot of comments to make it more understandable ( and in case I forget the logic someday ) :

``````public class Solution {
public boolean isMatch(String s, String p) {
return isMatch(s, 0, s.length() - 1, p, 0, p.length() - 1);
}

public boolean isMatch(String s, int sS, int sE, String p, int pS, int pE) {
// empty string , no pattern: can match
if (sS > sE && pS > pE)
return true;

// non-empty string,  no pattern: cannot match
if (sS <= sE && pS > pE)
return false;

// empty string, non-empty pattern: test if the pattern can match an empty string
if (sS > sE && pS <= pE)
return canMatchEmpty(p, pS, pE);

// algorithm begins:

// 1. if the first 2 chars of pattern are "a*" or ".*":
if (pS + 1 <= pE && p.charAt(pS + 1) == '*') {

// because "a*" or ".*" can match an empty string,
// if the rest part of the pattern can match the whole string,
// we know the whole pattern can match it too.
if (isMatch(s, sS, sE, p, pS + 2, pE))
return true;

// "a*" or ".*" can match a bunch of chars too, so for every position
// in string, we test:
// 1. whether the left part can match this 'sterisk' pattern (which has only two chars)
// 2. whether the right part (may be an empty string) can match the rest part of the pattern
for (int i = sS; i <= sE; i++) {
if (matchSterisk(s, sS, i, p.charAt(pS))
&& isMatch(s, i + 1, sE, p, pS + 2, pE))
return true;
}

// match failed
return false;
}

// 2. the first char of pattern is '.':
if (p.charAt(pS) == '.') {
// a '.' can match any single number, so we can safely skip it
return isMatch(s, sS + 1, sE, p, pS + 1, pE);
}

// 3. the first char of pattern is a letter:
return s.charAt(sS) == p.charAt(pS)
&& isMatch(s, sS + 1, sE, p, pS + 1, pE);
}

// if a pattern can match empty string, it should be like 'a*a*.*b*'
private boolean canMatchEmpty(String p, int pS, int pE) {
if (!(pE - pS >= 1 && (pE - pS + 1) % 2 == 0))
return false;
for (int i = 0; i <= pE - pS; i++) {
if (i % 2 == 0 && p.charAt(pS + i) == '*')
return false;
if (i % 2 == 1 && p.charAt(pS + i) != '*')
return false;
}
return true;
}

// test whether a string can match a sterisk pattern, which is like c + '*'
private boolean matchSterisk(String s, int sS, int sE, char c) {
if (c == '.')
return true;
for (int i = sS; i <= sE; i++) {
if (s.charAt(i) != c)
return false;
}
return true;
}
}``````

• Take a look at my solution.

``````    public boolean isMatch(String s, String p) {
if (s==null&&p==null) return true;

if (s.length()==0&&p.length()==0) return true;

boolean[][] matrix = new boolean[s.length()+1][p.length()+1];

matrix[0][0]=true;

for (int i=1;i<=s.length();i++)
matrix[i][0]=false;

for (int j=1;j<=p.length();j++)
if (p.charAt(j-1)=='*'&&j>1)
matrix[0][j]=matrix[0][j-2];
else matrix[0][j]=false;

for (int i=1;i<=s.length();i++)
for (int j=1;j<=p.length();j++)

if (p.charAt(j-1)==s.charAt(i-1)||p.charAt(j-1)=='.')
matrix[i][j]=matrix[i-1][j-1];

else if (p.charAt(j-1)=='*'&&j>1)
if (p.charAt(j-2)==s.charAt(i-1)||p.charAt(j-2)=='.')
matrix[i][j]=matrix[i-1][j]||matrix[i][j-2]||matrix[i][j-1];
//matrix[i-1][j]:abb vs ab*: depends on ab vs ab*
//matrix[i][j-2] a  vs ab*  depends on a vs a
//matrix[i][j-1] ab vs ab*: depends on ab vs ab
else
matrix[i][j]=matrix[i][j-2];

else matrix[i][j]=false;

return matrix[s.length()][p.length()];
}``````

• Hi, @reeclapple, can you add some explanation of your solution? I am confused.

• Thank you!!! It took me a while to get the logic.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.