Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public boolean isMatchTLE(String s, String p) {
- if (s == null || p == null) {
- return false;
- }
- return isMatchHelper(s, 0, p, 0);
- }
- // b*b*ab**ba*b**b***bba , this should trim some of the recursion time
- public String removeDuplicateStars(String p) {
- String newP = "";
- for (int i = 0; i < p.length(); i++) {
- if (p.charAt(i) != '*') {
- newP += p.charAt(i);
- } else {
- if (newP.length() == 0 || newP.charAt(newP.length() - 1) != '*') {
- newP += "*";
- }
- }
- }
- return newP;
- }
- // Even after all those optimizations, this would still TLE, n*2^m
- private boolean isMatchHelper(String s, int i, String p, int j) {
- if (j == p.length()) {
- return i == s.length();
- }
- p = this.removeDuplicateStars(p);
- if (p.charAt(j) == '*') {
- // s = "abcdef"
- // p = "*bc*def"
- if (isMatchHelper(s, i, p, j + 1)) {
- return true;
- }
- if (i == s.length() - 1 && j == p.length() - 1) {
- return true;
- }
- for (int k = i + 1; k < s.length(); k++) {
- return isMatchHelper(s, k, p, j);
- }
- } else {
- if (isCharMatch(s, i, p, j)) {
- return isMatchHelper(s, i + 1, p, j + 1);
- }
- return false;
- }
- return false;
- }
- // compare if char is the same or it is a '?'
- private boolean isCharMatch(String s, int i, String p, int j) {
- if (i >= s.length() || j >= p.length()) {
- return false;
- }
- return s.charAt(i) == p.charAt(j) || p.charAt(j) == '?';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement