BruteForce

bruteforce.java

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) == '?';
	}