leetcode: Wildcard Matching solution | Sigmainfy 烟客旅人

leetcode: Wildcard Matching solution | Sigmainfy 烟客旅人

Wildcard Matching Problem Description:

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

Wildcard Matching Solution and Precautions:

(1) recursive solution or DP, F(i, j) denote if s[0]…s[i-1] and p[0]…p[j-1] is matched or not

 F(i, j) = (s[i-1] == p[j-1]) && F(i-1, j-1) if  p[j-1] != '*' or '?'
F(i, j) = F(i-1, j-1)  if  p[j] == '?'
F(i, j) = OR F(i-l, j-1) for l = 0, … i,  if  p[j] == '*'

(2) greedy: whenever encounter '*' in p, keep record of the current position of '*' in p and the current index in s. Try to match the stuff behind this '*' in p with s, if not matched, just s++ and then try to match again.

Wildcard Matching Tips and Divergent thinking:

The dp version need to do memory optimization, otherwise OJ will report memory limit exceeds. Usually, only the greedy approach could pass OJ, the maximum size of the test case in OJ is around 30000^2.

Read full article from leetcode: Wildcard Matching solution | Sigmainfy 烟客旅人