Edlison

edlison.github.io

View My GitHub Profile

Wildcard Matching

Given an input string (s) and a pattern (p), 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).

Note:

s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like ? or *. 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’. Example 4:

Input: s = “adceb” p = “ab” Output: true Explanation: The first ‘’ matches the empty sequence, while the second ‘’ matches the substring “dce”. Example 5:

Input: s = “acdcb” p = “a*c?b” Output: false

class Solution {
  public boolean isMatch(String s, String p) {
    int sLen = s.length(), pLen = p.length();
    int sIdx = 0, pIdx = 0;
    int starIdx = -1, sTmpIdx = -1;

    while (sIdx < sLen) {

      if (pIdx < pLen && (p.charAt(pIdx) == '?' || p.charAt(pIdx) == s.charAt(sIdx))){
        ++sIdx;
        ++pIdx;
      }

      else if (pIdx < pLen && p.charAt(pIdx) == '*') {

        starIdx = pIdx;
        sTmpIdx = sIdx;
        ++pIdx;
      }

      else if (starIdx == -1) {
        return false;
      }

      else {

        pIdx = starIdx + 1;
        sIdx = sTmpIdx + 1;
        sTmpIdx = sIdx;
      }
    }

    for(int i = pIdx; i < pLen; i++)
      if (p.charAt(i) != '*') return false;
    return true;
  }
}

Reference
https://leetcode-cn.com/problems/wildcard-matching/