LeetCode-44-通配符匹配

LeetCode-44-通配符匹配

44. 通配符匹配

給定一個字符串 (s) 和一個字符模式 (p) ，實現(xiàn)一個支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何單個字符。
'*' 可以匹配任意字符串（包括空字符串）。

兩個字符串完全匹配才算匹配成功。

說明:

  • s 可能為空，且只包含從 a-z 的小寫字母。
  • p 可能為空，且只包含從 a-z 的小寫字母，以及字符 ? 和 *。

示例 1:

輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個字符串。

示例 2:

輸入:
s = "aa"
p = "*"
輸出: true
解釋: '*' 可以匹配任意字符串。

示例 3:

輸入:
s = "cb"
p = "?a"
輸出: false
解釋: '?' 可以匹配 'c', 但第二個 'a' 無法匹配 'b'。

示例 4:

輸入:
s = "adceb"
p = "*a*b"
輸出: true
解釋: 第一個 '*' 可以匹配空字符串, 第二個 '*' 可以匹配字符串 "dce".

示例 5:

輸入:
s = "acdcb"
p = "a*c?b"
輸出: false
  1. Wildcard Matching

Hard

2951140Add to ListShare

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

解題思路：一個樣本做行，一個樣本做列的動態(tài)規(guī)劃模型。

先寫出遞歸解法函數(shù)

定義函數(shù) public static boolean process1(char[] s, char[] p, int si, int pi) 表示字符串S從[si,s.length]能夠被p從[pi,p.length] 匹配出來，函數(shù)返回true 否則 返回false。

那主函數(shù)就可以 調(diào)用process1來解決本題

class Solution {
    public boolean isMatch(String s, String p) {
        char[] s = str.toCharArray();
        char[] p = pattern.toCharArray();
        return process1(s, p, 0, 0);
    }
}

接下來解決遞歸遍歷字符串邏輯

  • if (si == s.length)

表示 s->"" s為空串 那么pi為什么才能匹配？

**pi 為空可以匹配 **即 pi == p.length

或者 （ '*' 可以匹配任意字符串（包括空字符串）。）

[pi] ==* 則函數(shù)就遞歸到pi+1 的位置匹配 即 p[pi] == '*' && process1(s, p, si, pi + 1);

public static boolean process1(char[] s, char[] p, int si, int pi) {
    if (si == s.length) { // s -> ""
            if (pi == p.length) { // p -> ""
                return true;
            } else {
                // p -> "..."
                // p[pi] == '*' && p[pi+1...] -> "
                return p[pi] == '*' && process1(s, p, si, pi + 1);
            }
    }
}
  • if (pi == p.length)

表示 p 剩下的為"" 空串，只有si == s.length 才能匹配

public static boolean process1(char[] s, char[] p, int si, int pi) {
        if (si == s.length) { // s -> ""
            if (pi == p.length) { // p -> ""
                return true;
            } else {
                // p -> "..."
                // p[pi] == '*' && p[pi+1...] -> "
                return p[pi] == '*' && process1(s, p, si, pi + 1);
            }
        }
        if (pi == p.length) { // p -> "" s=="" return true
            return si == s.length;
        }
}
  • s從si出發(fā).... p從pi出發(fā)...

s[si] -> 小寫字母

p[pi] -> 小寫、?、*

此時 s[si] 為任意 一個小寫字母， p[pi] 為 任意 一個小寫字母|？|* 三種情況

如果 if (p[pi] != '?' && p[pi] != '*')

image-20210509144216902
public static boolean process1(char[] s, char[] p, int si, int pi) {
        if (si == s.length) { // s -> ""
            if (pi == p.length) { // p -> ""
                return true;
            } else {
                // p -> "..."
                // p[pi] == '*' && p[pi+1...] -> "
                return p[pi] == '*' && process1(s, p, si, pi + 1);
            }
        }
        if (pi == p.length) { // p -> "" s=="" return true
            return si == s.length;
        }
        // s從si出發(fā).... p從pi出發(fā)...
        // s[si] -> 小寫字母
        // p[pi] -> 小寫、?、*
        if (p[pi] != '?' && p[pi] != '*') {
            return s[si] == p[pi] && process1(s, p, si + 1, pi + 1);
        }
}
  • s從si出發(fā).... p從pi出發(fā)...

s[si] -> 小寫字母

p[pi] -> 小寫、?、*

此時 s[si] 為任意 一個小寫字母， p[pi] ==？|* 兩種情況

if (p[pi] == '?')

image-20210509144615628
public static boolean process1(char[] s, char[] p, int si, int pi) {
        if (si == s.length) { // s -> ""
            if (pi == p.length) { // p -> ""
                return true;
            } else {
                // p -> "..."
                // p[pi] == '*' && p[pi+1...] -> "
                return p[pi] == '*' && process1(s, p, si, pi + 1);
            }
        }
        if (pi == p.length) { // p -> "" s=="" return true
            return si == s.length;
        }
        // s從si出發(fā).... p從pi出發(fā)...
        // s[si] -> 小寫字母
        // p[pi] -> 小寫、?、*
        if (p[pi] != '?' && p[pi] != '*') {
            return s[si] == p[pi] && process1(s, p, si + 1, pi + 1);
        }
        // si.. pi.. pi ? *
        if (p[pi] == '?') {
            return process1(s, p, si + 1, pi + 1);
        }
}
  • s從si出發(fā).... p從pi出發(fā)...

s[si] -> 小寫字母

p[pi] -> 小寫、?、*

此時 s[si] 為任意 一個小寫字母， p[pi] * 的情況

'*' 可以匹配任意字符串（包括空字符串）

image-20210509145058425
public static boolean process1(char[] s, char[] p, int si, int pi) {
        if (si == s.length) { // s -> ""
            if (pi == p.length) { // p -> ""
                return true;
            } else {
                // p -> "..."
                // p[pi] == '*' && p[pi+1...] -> "
                return p[pi] == '*' && process1(s, p, si, pi + 1);
            }
        }
        if (pi == p.length) { // p -> "" s=="" return true
            return si == s.length;
        }
        // s從si出發(fā).... p從pi出發(fā)...
        // s[si] -> 小寫字母
        // p[pi] -> 小寫、?、*
        if (p[pi] != '?' && p[pi] != '*') {
            return s[si] == p[pi] && process1(s, p, si + 1, pi + 1);
        }
        // si.. pi.. pi ? *
        if (p[pi] == '?') {
            return process1(s, p, si + 1, pi + 1);
        }
        //'*' 可以匹配任意字符串（包括空字符串）所有可能性都需要嘗試
        for (int len = 0; len <= s.length - si; len++) {
            if (process1(s, p, si + len, pi + 1)) {
                return true;
            }
        }
    return false;
}

遞歸嘗試了所有可能性

class Solution {
    public static boolean isMatch(String str, String pattern) {
        char[] s = str.toCharArray();
        char[] p = pattern.toCharArray();
        return process1(s, p, 0, 0);
    }

    // s[si....] 能否被 p[pi....] 匹配出來
    public static boolean process1(char[] s, char[] p, int si, int pi) {
        if (si == s.length) { // s -> ""
            if (pi == p.length) { // p -> ""
                return true;
            } else {
                // p -> "..."
                // p[pi] == '*' && p[pi+1...] -> "
                return p[pi] == '*' && process1(s, p, si, pi + 1);
            }
        }
        if (pi == p.length) { // p -> "" s
            return si == s.length;
        }
        // s從si出發(fā).... p從pi出發(fā)...
        // s[si] -> 小寫字母
        // p[pi] -> 小寫、?、*
        if (p[pi] != '?' && p[pi] != '*') {
            return s[si] == p[pi] && process1(s, p, si + 1, pi + 1);
        }
        // si.. pi.. pi ? *
        if (p[pi] == '?') {
            return process1(s, p, si + 1, pi + 1);
        }
        for (int len = 0; len <= s.length - si; len++) {
            if (process1(s, p, si + len, pi + 1)) {
                return true;
            }
        }
        return false;
    }
}
image-20210509145342796
image-20210509145403901

說明算法思路沒有問題，只是算法測試時間超標了，通過動態(tài)規(guī)劃來優(yōu)化，使用si 做行 di 做列的動態(tài)規(guī)劃優(yōu)化

public static boolean isMatch(String str, String pattern) {
        char[] s = str.toCharArray();
        char[] p = pattern.toCharArray();
        int N = s.length;
        int M = p.length;
        boolean[][] dp = new boolean[N + 1][M + 1];
        return dp[0][0];
}

如果我們把dp數(shù)組的值填好了，返回return dp[0][0]，就能表示process1(char[] s, char[] p, 0, 0)是否匹配

  • dp[N][M] = true;
if (si == s.length) { // s -> ""
            if (pi == p.length) { // p -> ""
                return true;//  dp[N][M] = true;
            } else {
                return p[pi] == '*' && process1(s, p, si, pi + 1);//dp[N][pi] = p[pi] == '*' && dp[N][pi + 1];
            }
        }
image
if (pi == p.length) { // p -> "" s
            return si == s.length;
        }
image-20210509150823869
public static boolean isMatch(String str, String pattern) {
        char[] s = str.toCharArray();
        char[] p = pattern.toCharArray();
        int N = s.length;
        int M = p.length;
        boolean[][] dp = new boolean[N + 1][M + 1];
    
        dp[N][M] = true;
        for (int pi = M - 1; pi >= 0; pi--) {
            dp[N][pi] = p[pi] == '*' && dp[N][pi + 1];
        }
    
        return dp[0][0];
}
image-20210509151124135
        if (p[pi] != '?' && p[pi] != '*') {
            return s[si] == p[pi] && process1(s, p, si + 1, pi + 1);
        }
        // si.. pi.. pi ? *
        if (p[pi] == '?') {
            return process1(s, p, si + 1, pi + 1);
        }
        for (int len = 0; len <= s.length - si; len++) {
            if (process1(s, p, si + len, pi + 1)) {
                return true;
            }
        }
  • if (p[pi] != '?' && p[pi] != '*')
image-20210509151546795
  • if (p[pi] == '?')
image-20210509151823476
  • if (p[pi] == '*?')
image-20210509153432236
class Solution {
    public static boolean isMatch(String str, String pattern) {
        char[] s = str.toCharArray();
        char[] p = pattern.toCharArray();
        int N = s.length;
        int M = p.length;
        boolean[][] dp = new boolean[N + 1][M + 1];
    
        dp[N][M] = true;
        for (int pi = M - 1; pi >= 0; pi--) {
            dp[N][pi] = p[pi] == '*' && dp[N][pi + 1];
        }
    
        for (int si = N - 1; si >= 0; si--) {
            for (int pi = M - 1; pi >= 0; pi--) {
                if (p[pi] != '?' && p[pi] != '*') {
                    dp[si][pi] = s[si] == p[pi] && dp[si + 1][pi + 1];
                    continue;
                }
                if (p[pi] == '?') {
                    dp[si][pi] = dp[si + 1][pi + 1];
                    continue;
                }
                for (int len = 0; len <= N - si; len++) {
                    if (dp[si + len][pi + 1]) {
                        dp[si][pi] = true;
                        break;
                    }
                }
            }
        }
        return dp[0][0];
    }
}
image-20210509153844896

斜率優(yōu)化

p[pi] == '*'

image-20210509154345378
class Solution {
    public static boolean isMatch(String str, String pattern) {
        char[] s = str.toCharArray();
        char[] p = pattern.toCharArray();
        int N = s.length;
        int M = p.length;
        boolean[][] dp = new boolean[N + 1][M + 1];
    
        dp[N][M] = true;
        for (int pi = M - 1; pi >= 0; pi--) {
            dp[N][pi] = p[pi] == '*' && dp[N][pi + 1];
        }
    
        for (int si = N - 1; si >= 0; si--) {
            for (int pi = M - 1; pi >= 0; pi--) {
                if (p[pi] != '?' && p[pi] != '*') {
                    dp[si][pi] = s[si] == p[pi] && dp[si + 1][pi + 1];
                    continue;
                }
                if (p[pi] == '?') {
                    dp[si][pi] = dp[si + 1][pi + 1];
                    continue;
                }
                // p[pi] == '*'
                dp[si][pi] = dp[si][pi + 1] || dp[si + 1][pi];
            }
        }
        return dp[0][0];
    }
}
image-20210509154051313
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容