wildcardMatching.java

// This is the DP solution, and falls perfectly using the DP template
	// Also this is only boolean answer (not find all steps) || find the extreme values (min,max)
	public boolean isMatch(String s, String p) {
		if (s == null || p == null) {
			return false;
		}
		int row = s.length();
		int col = p.length();
		boolean[][] lookup = new boolean[row + 1][col + 1];

		lookup[0][0] = true;
		// initialize lookup init values, for the string (s) part, it all default to false
		// since a char matches to empty is false anyway
		for (int j = 1; j <= col; j++) {
			if (p.charAt(j - 1) == '*' && lookup[0][j - 1]) {
				lookup[0][j] = true;
			}
		}

		for (int i = 1; i <= row; i++) {
			for (int j = 1; j <= col; j++) {
				if (p.charAt(j - 1) == '*') {
					lookup[i][j] = lookup[i][j - 1] || lookup[i - 1][j];
				} else {
					if (lookup[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?')) {
						lookup[i][j] = true;
					}
				}

			}
		}
		return lookup[row][col];
	}