0044. Wildcard Matching

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

Description

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'.

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

Constraints:

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

ac1: 2D dp

similar with #10

class Solution {
    public boolean isMatch(String s, String p) {
        // edge cases
        if (s == null || p == null) return false;

        // initialize
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        for (int i = 1; i < dp[0].length; i++) {
            // s is empty, p has to be all "*" to be true.
            if (p.charAt(i-1) == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }

        // walk, function transformation
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '?') {
                    dp[i][j] = dp[i-1][j-1];
                } 
                if (p.charAt(j-1) == '*') {
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                }
            }
        }

        // result
        return dp[s.length()][p.length()];
    }
}

/*
state: dp[i][j], s.substring(0, i) and p.substring(0, j) is match

function: 
1. if p.charAt(j-1) == s.charAt(i-1) , dp[i][j] = dp[i-1][j-1];
2. if p.charAt(j-1) == '?' , dp[i][j] = dp[i-1][j-1];
3. if p.charAt(j-1) == '*' : 
    (1) * means empty: dp[i][j] = dp[i][j-1];
    (2) * means anything: dp[i][j] = dp[i-1][j];

initialize: dp[0][0] = true; dp[0][i]

result: dp[s.length()][p.length()]
*/

ac2: 1D DP

Notice: 1D dp, need to update each one in the array, because it does not have default value, unlike 2D dp. else dp[j] = false;

class Solution {
    public boolean isMatch(String s, String p) {
        // edge cases
        if (s == null || p == null) return false;

        // initialize
        boolean[] dp = new boolean[p.length()+1];
        dp[0] = true;
        for (int i = 1; i < dp.length; i++) {
            if (p.charAt(i-1) == '*') {
                dp[i] = true;
            } else {
                break;
            }
        }

        // walk, function transformation
        for (int i = 1; i <= s.length(); i++) {
            boolean prev = dp[0];
            dp[0] = false;

            for (int j = 1; j < dp.length; j++) {
                boolean tmp = dp[j];
                if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '?') {
                    dp[j] = prev;
                } else if (p.charAt(j-1) == '*') {
                    dp[j] = dp[j-1] || dp[j];
                } else {
                    dp[j] = false;
                }
                prev = tmp;
            }
        }

        // result
        return dp[p.length()];
    }
}

ac3: 2 pointers

class Solution {
    public boolean isMatch(String s, String p) {
        // edge cases
        if (s == null || p == null) return false;

        // 2 pointers, walk
        int si = 0, pi = 0, starIndex = -1, sRestart = 0;
        while (si < s.length()) {
            if (pi < p.length() && (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '?') ) {
                si++;
                pi++;
            } 

            else if (pi < p.length() && p.charAt(pi) == '*') {
                starIndex = pi;
                sRestart = si;
                pi++;
            }
            // s.charAt(si) != p.charAt(pi)
            else if (starIndex != -1) { // meet * before, let * kill one char in s
                sRestart++;
                si = sRestart;
                pi = starIndex + 1;
            }

            else {
                return false;
            }
        }

        // check pattern remaining 
        while (pi < p.length() && p.charAt(pi) == '*') {
            pi++;
        }

        // if match, pi should hit the end of pattern
        return pi == p.length();
    }
}

/*
2 pointers

si, pi

if s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '?' , move on, si++; pi++;
if p.charAt(pi) == '*': meet * , starI = pi, sRestart = si(in case * will offset chars in s), pi++
if s.charAt(si) != p.charAt(pi):
    1) have * before starI != -1 : '*' can kill char in s one by one
        sRestart++; si = sRestart; (the * offset one char in s)
        pi = starI + 1; 
    2) don't have *, return false;

abededab
?b*d**

a=?, go on, b=b, go on,
e=*, save * position star=3, save s position ss = 3, p++
e!=d,  check if there was a *, yes, ss++, s=ss; p=star+1 // the * offset 'e'
d=d, go on, meet the end.
check the rest element in p, if all are *, true, else false;


*/

Description

ac1: 2D dp

ac2: 1D DP

ac3: 2 pointers

Similar problems