44.Wildcard-Matching

44. Wildcard Matching

题目地址

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

https://blog.csdn.net/jmspan/article/details/51460021

题目描述

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 = "*a*b"
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

代码

Approach 1: DFS

class Solution {
  public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;
    if (s.length() == 0 || p.length() == 0)    return false;

    return dfs(s, 0, p, 0);
  }

  private boolean dfs(String s, int sIdx, String p, int pIdx) {
    if (sIdx == s.length() || pIdx == p.length()) {
      if (sIdx == s.length() && pIdx == p.length()) {
        return true;
      } else {
        return false;
      }
    }

    if (p.charAt(pIdx) == '*') {
      // remove continuous *
      while (p.charAt(pIdx) == '*')
          pIdx++;
        if (pIdx == p.length())    return true;
      }

            // compare remaining part of p after * with s
      while (sIdx < s.length() && !dfs(s, sIdx, p, pIdx)) {
        sIdx++;
      }

      // sIdx 不能为空
      return sIdx != s.length();
    } else if (s.charAt(sIdx) == p.chaAt(pIdx) || p.charAt(pIdx) == '?') {
      return dfs(s, sIdx + 1, p, pIdx + 1);
    } else {
      return false;
    }
    }
}

Approach #2 Dynamic Programming

Time complexity : O(SP) && Space complexity : O(SP) to keep the matrix.

class Solution {
  public boolean isMatch(String s, String p) {
    int sLen = s.length(), pLen = p.length();

    // base cases
    if (p.equals(s) || p.equals("*")) return true;
    if (p.isEmpty() || s.isEmpty()) return false;

    // init all matrix except [0][0] element as False
    boolean[][] d = new boolean[pLen + 1][sLen + 1];
    d[0][0] = true;

    // DP compute
    for (int pIdx = 1; pIdx < pLen + 1; pIdx++) {
      // the current character in the pattern is '*'
      if (p.charAt(pIdx - 1) == '*') {
        int sIdx = 1;
        // d[p_idx - 1][s_idx - 1] is a string-pattern match
        // on the previous step, i.e. one character before.
        // Find the first idx in string with the previous math.
        while ((!d[pIdx - 1][sIdx - 1]) && (sIdx < sLen + 1))     sIdx++;
        // If (string) matches (pattern),
        // when (string) matches (pattern)* as well
        d[pIdx][sIdx - 1] = d[pIdx - 1][sIdx - 1];
        // If (string) matches (pattern),
        // when (string)(whatever_characters) matches (pattern)* as well
        while (sIdx < sLen + 1)     d[pIdx][sIdx++] = true;
      }
      // the current character in the pattern is '?'
      else if (p.charAt(pIdx - 1) == '?') {
        for (int sIdx = 1; sIdx < sLen + 1; sIdx++)
          d[pIdx][sIdx] = d[pIdx - 1][sIdx - 1];
      }
      // the current character in the pattern is not '*' or '?'
      else {
        for (int sIdx = 1; sIdx < sLen + 1; sIdx++) {
          // Match is possible if there is a previous match
          // and current characters are the same
          d[pIdx][sIdx] = d[pIdx - 1][sIdx - 1] &&
                  (p.charAt(pIdx - 1) == s.charAt(sIdx - 1));
        }
      }
    }
    return d[pLen][sLen];
  }
}

Approach #3 Dynamic Programming - 2

boolean strmatch(String str, String pattern, int n, int m) { 
        // empty pattern can only match with 
        // empty string 
        if (m == 0) 
            return (n == 0); 

        // lookup table for storing results of 
        // subproblems 
        boolean[][] lookup = new boolean[n + 1][m + 1]; 

        // initailze lookup table to false 
        for(int i = 0; i < n + 1; i++) 
            Arrays.fill(lookup[i], false); 


        // empty pattern can match with empty string 
        lookup[0][0] = true; 

        // Only '*' can match with empty string 
        for (int j = 1; j <= m; j++) 
            if (pattern.charAt(j - 1) == '*') 
                lookup[0][j] = lookup[0][j - 1]; 

        // fill the table in bottom-up fashion 
        for (int i = 1; i <= n; i++) 
        { 
            for (int j = 1; j <= m; j++) 
            { 
                // Two cases if we see a '*' 
                // a) We ignore '*'' character and move 
                //    to next  character in the pattern, 
                //     i.e., '*' indicates an empty sequence. 
                // b) '*' character matches with ith 
                //     character in input 
                if (pattern.charAt(j - 1) == '*') 
                    lookup[i][j] = lookup[i][j - 1] || 
                                   lookup[i - 1][j]; 

                // Current characters are considered as 
                // matching in two cases 
                // (a) current character of pattern is '?' 
                // (b) characters actually match 
                else if (pattern.charAt(j - 1) == '?' || 
                    str.charAt(i - 1) == pattern.charAt(j - 1)) 
                    lookup[i][j] = lookup[i - 1][j - 1]; 

                // If characters don't match 
                else lookup[i][j] = false; 
            } 
        } 

        return lookup[n][m]; 
    }

Approach #3 Backtracking

Time complexity : O(min(S,P)) && Space complexity : O(1)

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 the pattern caracter = string character
      // or pattern character = '?'
      if (pIdx < pLen && (p.charAt(pIdx) == '?' || p.charAt(pIdx) == s.charAt(sIdx))){
        ++sIdx;
        ++pIdx;
      }
      // If pattern character = '*'
      else if (pIdx < pLen && p.charAt(pIdx) == '*') {
        // Check the situation
        // when '*' matches no characters
        starIdx = pIdx;
        sTmpIdx = sIdx;
        ++pIdx;
      }
      // If pattern character != string character
      // or pattern is used up
      // and there was no '*' character in pattern 
      else if (starIdx == -1) {
        return false;
      }
      // If pattern character != string character
      // or pattern is used up
      // and there was '*' character in pattern before
      else {
        // Backtrack: check the situation
        // when '*' matches one more character
        pIdx = starIdx + 1;
        sIdx = sTmpIdx + 1;
        sTmpIdx = sIdx;
      }
    }

    // The remaining characters in the pattern should all be '*' characters
    for (int i = pIdx; i < pLen; i++)
      if (p.charAt(i) != '*') return false;
    return true;
  }
}