My Java accepted solution. Parsing expression to tokens then use DP

• I parsed the expression into tokens like "a", "." and "a*" and then used dp for matching the string with the tokens. match[i][j] represents whether s.substring(0, i) matches with the tokens from index 0 to index j-1.

``````public class Solution {
public boolean isMatch(String s, String p) {
if (s == null && p == null || s.length() == 0 && p.length() == 0) {
return true;
}
if (s == null || p == null) {
return false;
}
List<String> tokens = parse(p);
boolean[][] match = new boolean[s.length()+1][tokens.size()+1];
match[0][0] = true;
int match_len = s.length() + 1;
int token_len = tokens.size() + 1;

// Initialize match for dp iteration
for (int i = 1; i < match_len; i++) {
match[i][0] = false;
}
for (int i = 1; i < token_len; i++) {
match[0][i] = match[0][i-1] && tokens.get(i-1).length() == 2;
}

// dp
for (int i = 1; i < match_len; i++) {
for (int j = 1; j < token_len; j++) {
String curr = tokens.get(j-1);
match[i][j] = curr.length() == 2 && match[i][j-1] ||
curr.length() == 2 && (curr.charAt(0) == '.' || curr.charAt(0) == s.charAt(i-1)) && match[i-1][j] ||
(curr.charAt(0) == '.' || curr.charAt(0) == s.charAt(i-1)) && match[i-1][j-1];
}
}
return match[match_len-1][token_len-1];
}

// Parse the expression into length one or length two tokens.
public List<String> parse(String p) {
int i = 0;
List<String> result = new ArrayList<String>();
while (i < p.length()) {
if (p.charAt(i) == '*') {
i++;
} else {
if (i + 1 >= p.length() || p.charAt(i+1) != '*') {
i++;
} else if (p.charAt(i+1) == '*') {
i += 2;
}
}
}
return result;
}

}``````

• I really don't know how this solution is accepted..
I couldn't type it out, because the 'star' character will be automatically omitted by the system after I submitted the commet. So, I use [star] instead of typing it, try this:
s = "[star]ac", p ="[star]a.[star]"
Apparently, they match! But this solution returns false. Check it out.

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