[LeetCode] 44. Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "*") ? true
isMatch("aa", "a*") ? true
isMatch("ab", "?*") ? true
isMatch("aab", "c*a*b") ? false

Thought process:
Recursively match s and p's substrings.

1. Base case:
1. If s and p are both empty, return true.
2. If p's length is 1:
1. If p is *, return true.
2. If p is ? and s's length is 1, return true.
3. Else if s and p are equal, return true.
2. Recurrence:
1. If p's first character is *:
1. If s match p[1, ...], then * matches an empty sequence. Return true.
2. Otherwise, check if s[1, ...] matches p.
2. Otherwise, check if their first characters match, and recursively check s[1, ...] and p[1, ...].

Solution 1 (backtracking):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public class Solution { public boolean isMatch(String s, String p) { if (p.length() == 0) { return s.length() == 0; } if (p.length() == 1) { if (p.equals("*")) { return true; } return s.length() == 1 && (p.equals("?") || s.equals(p)); } if (p.charAt(0) == '*') { if (isMatch(s, p.substring(1))) { return true; } return s.length() > 0 && isMatch(s.substring(1), p); } return s.length() > 0 && (p.charAt(0) == '?' || s.charAt(0) == p.charAt(0)) && isMatch(s.substring(1), p.substring(1)); } }

Time complexity:
O(sp). This solution exceeds the time limit.

To improve the efficiency of my solution, I can match the characters iteratively. Use two pointers, one iterates s, the other iterates p, and match the characters one by one. There is a greedy element in this problem, which is that as long as the last character I saw in p is *, I can advance s's pointer even if it doesn't match p's.

Solution 2 (greedy):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

public class Solution { public boolean isMatch(String s, String p) { int i = 0; int j = 0; int star = -1; int matched = 0; nc while (i < s.length()) { if (j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) { i++; j++; } else if (j < p.length() && p.charAt(j) == '*') { star = j; matched = i; j++; } else if (star != -1) { matched++; i = matched; j = star + 1; } else { return false; } } while (j < p.length() && p.charAt(j) == '*') { j++; } return j == p.length(); } }

Time complexity: O(s + p).

There is another solution using DP.

1. Sub-problem: if a sub-string of p is a match of a sub-string of s.
2. Function: 
1. If s[i] == p[j] or p[j] == '?', f[i][j] = f[i - 1][j - 1].
2. Else if p[j] == '*', f[i][j] = f[i][j - 1] (empty sequence) or f[i - 1][j - 1] (one character) or f[i - 1][j] (multiple characters).
3. Initialization: f[0][0] = true. String is the rows and pattern is the columns. Iterate through the first row. While p[i] == '*', set f[0][i] = true.
4. Answer: f[s length][p length].

Solution 3 (DP):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public boolean isMatch(String s, String p) { boolean[][] f = new boolean[s.length() + 1][p.length() + 1]; f[0][0] = true; for (int i = 0; i < p.length(); i++) { if (p.charAt(i) != '*') { break; } f[0][i + 1] = true; } for (int i = 0; i < s.length(); i++) { for (int j = 0; j < p.length(); j++) { if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') { f[i + 1][j + 1] = f[i][j]; } else if (p.charAt(j) == '*') { f[i + 1][j + 1] = (f[i + 1][j] || f[i][j] || f[i][j + 1]); } } } return f[s.length()][p.length()]; } }

Time complexity: O(ps).