44. Wildcard Matching

Problem

Tags: String, Dynamic Programming, Greedy, Recursion

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

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

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

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Constraints:

• 0 <= s.length, p.length <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, '?' or '*'.

Solution

Solution

The most difficult part of this problem is '*', when we meet it, we don't know how many chars we should match.

So, we store a position to "come back" after the current match failed.

Code

C

// 44. Wildcard Matching (12/10/54169)
// Runtime: 8 ms (67.76%) Memory: 5.79 MB (76.50%) 

bool isMatch(char* str, char* pat) {
    int str_len = strlen(str), pat_len = strlen(pat);
    int str_idx = 0, pat_idx = 0;
    int str_idx_retry = 0, pat_idx_retry = 0;

    while (str_idx < str_len || pat_idx < pat_len) {
        // printf("---\nstr: %s\npat: %s\n", str + str_idx, pat + pat_idx);
        if (pat_idx < pat_len) {
            if (pat[pat_idx] == '*') {
                pat_idx_retry = pat_idx;
                str_idx_retry = str_idx + 1;
                pat_idx++;
                continue;
            }
            else if (pat[pat_idx] == '?' && str_idx < str_len) {
                str_idx++, pat_idx++;
                continue;
            }
            else if (str[str_idx] == pat[pat_idx]) {
                str_idx++, pat_idx++;
                continue;
            }
        }

        if (str_idx_retry > 0 && str_idx_retry <= str_len) {
            str_idx = str_idx_retry;
            pat_idx = pat_idx_retry;
            continue;
        }

        return false;
    }

    return true;
}

GO

// 44. Wildcard Matching (10/24/54169)
// Runtime: 8 ms (79.38%) Memory: 2.87 MB (89.38%) 

func isMatch(target string, pattern string) bool {
	target_idx, pattern_idx := 0, 0
	target_idx_retry, pattern_idx_retry := 0, 0

	for pattern_idx < len(pattern) || target_idx < len(target) {
		if pattern_idx < len(pattern) {
			c := pattern[pattern_idx]
			switch c {
			case '?':
				if target_idx < len(target) {
					pattern_idx++
					target_idx++
					continue
				}
			case '*':
				pattern_idx_retry = pattern_idx
				target_idx_retry = target_idx + 1
				pattern_idx++
				continue
			default:
				if target_idx < len(target) && target[target_idx] == c {
					pattern_idx++
					target_idx++
					continue
				}
			}
		}
        
		if 0 < target_idx_retry && target_idx_retry <= len(target) {
			pattern_idx = pattern_idx_retry
			target_idx = target_idx_retry
			continue
		}
		
		return false
	}

	return true
}