Leetcode Problem 44. Wildcard Matching

44. Wildcard Matching

Leetcode Solutions

Backtracking with Two Pointers

  1. Initialize two pointers s_idx and p_idx to 0, and variables star_idx and s_tmp_idx to -1.
  2. Iterate over the string with s_idx while s_idx < s.length().
  3. If p_idx < p.length() and the characters at s_idx and p_idx match (or p[p_idx] is ?), increment both s_idx and p_idx.
  4. If p_idx < p.length() and p[p_idx] is *, record the star position in star_idx, increment p_idx, and set s_tmp_idx to s_idx.
  5. If there is a mismatch (or p_idx is at the end), check if there was a previous * by looking at star_idx.
  6. If there was a previous *, backtrack: set p_idx to star_idx + 1, increment s_tmp_idx, and set s_idx to s_tmp_idx.
  7. If no match is found and no previous * exists, return False.
  8. After the loop, if p_idx is not at the end, check if the remaining characters in p are all *.
  9. Return True if all remaining characters in p are *; otherwise, return False.
UML Thumbnail

Dynamic Programming

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...