1. If the corresponding char in s and p are the same, or char_p == '?', then pass, we move to the next char.
2. If char_p == '*', since '*' can represent multiple characters, we store the '*' position in p (p_star) and the corresponding position in s (s_star). Since '*' can represent any sequence, at first we assume it represents empty sequence. So we increase index_p while preserve index_s.
3. It is possible that the next char after '*' is equal to '?' or is the same as the char in s, in this case, we follow condition 1.
4. In the case when p.charAt(index_p) != s.charAt(index_s). If there is a '*' in advance, we assume s.charAt(s_star) is represented by '*'. We increase s_star. Meanwhile, we return index_s to s_star + 1 and let index_p = p_star + 1 because we changed the match of '*' in s so we need to rematch every character after that.
5. If no '*' is found and p.charAt(index_p) != s.charAt(index_s), we return false.
s = "abefdgd"
p = "?b*?d"
I use 'x' - 'y' to represent the two characters match. 'x' !- 'y' for not matching
'a' - '?'
'b' - 'b'
'*': p_star = 2, s_star = 2, index_p++
'e' - '?'
'f' !- 'd', '*' exists, s_star = 3, index_s = 3, index_p = 3
'f' - '?'
'd' - 'd'
'*' exists, s_star = 4, index_s = 4, index_p = 3
'd' - '?'
'g' !- 'd', '*' exists, s_star = 5, index_s = 5, index_p = 3
'g' - '?'
'd' - 'd'
Update cleaner code version3:
public class Solution { public boolean isMatch(String s, String p) { if (s == null) return p == null; if (p == null) return s == null; if (p.length() == 0) return s.length() == 0; if (s.equals(p) || p.equals("*")) return true; int index_s = 0; int index_p = 0; int s_star = 0; int p_star = 0; boolean star = false; while (index_s < s.length()) { if (index_p < p.length() && (s.charAt(index_s) == p.charAt(index_p) || p.charAt(index_p) == '?')) { index_s++; index_p++; } else if (index_p < p.length() && p.charAt(index_p) == '*') { star = true; s_star = index_s; p_star = ++index_p; } else { if (!star) return false; index_p = p_star; index_s = ++s_star; } } while (index_p < p.length()) { if (p.charAt(index_p) != '*') return false; index_p++; } return true; } }
Update a cleaner code by using a boolean variable star.
public class WildCard { public boolean isMatch(String s, String p) { if (s == null || p == null) throw new NullPointerException("Null Pointer!"); if (p.equals("*")) return true; if (s.length() == 0) { for (int i = 0; i < p.length(); i++) { if (p.charAt(i) != '*') return false; } return true; } int index1 = 0; int index2 = 0; boolean star = false; int p_star = -1; int s_star = -1; while (index1 < s.length()) { if (index2 < p.length() && (s.charAt(index1) == p.charAt(index2) || p.charAt(index2) == '?')) { index1++; index2++; continue; } if (index2 < p.length() && p.charAt(index2) == '*') { star = true; p_star = index2; s_star = index1; index2++; continue; } if (star == false) return false; else { index1 = ++s_star; index2 = p_star + 1; } } while (index2 < p.length()) { if (p.charAt(index2) != '*') return false; index2++; } return true; } }
public class WildCard { public boolean isMatch(String s, String p) { if ((s == null && p != null) || (s != null && p == null)) return false; if (s == "") { for (int i = 0; i < p.length(); i++) { if (p.charAt(i) != '*') return false; } return true; } if (p.equals("*")) return true; int index_p = 0; int index_s = 0; int p_star = Integer.MAX_VALUE; int s_star = Integer.MAX_VALUE; while (index_s < s.length()) { if (index_p < p.length() && (s.charAt(index_s) == p.charAt(index_p) || p.charAt(index_p) == '?')) { index_s++; index_p++; continue; } if (index_p < p.length() && p.charAt(index_p) == '*') { s_star = index_s; p_star = index_p; index_p++; continue; } if (p_star != Integer.MAX_VALUE) { index_p = p_star + 1; index_s = ++s_star; continue; } return false; } while(index_p < p.length()) { if (p.charAt(index_p) != '*') return false; index_p++; } return true; } }
No comments:
Post a Comment