LeetCode-44-通配符匹配

44. 通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

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

两个字符串完全匹配才算匹配成功。

说明:

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

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

解题思路：一个样本做行，一个样本做列的动态规划模型。

先写出递归解法函数

定义函数 public static boolean process1(char[] s, char[] p, int si, int pi) 表示字符串S从[si,s.length]能够被p从[pi,p.length] 匹配出来，函数返回true 否则返回false。

那主函数就可以调用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] ==* 则函数就递归到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出发.... p从pi出发...

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出发.... p从pi出发...
        // s[si] -> 小写字母
        // p[pi] -> 小写、?、*
        if (p[pi] != '?' && p[pi] != '*') {
            return s[si] == p[pi] && process1(s, p, si + 1, pi + 1);
        }
}

s从si出发.... p从pi出发...

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出发.... p从pi出发...
        // 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出发.... p从pi出发...

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出发.... p从pi出发...
        // 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出发.... p从pi出发...
        // 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

说明算法思路没有问题，只是算法测试时间超标了，通过动态规划来优化，使用si 做行 di 做列的动态规划优化

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数组的值填好了，返回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];
            }
        }

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

斜率优化

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

LeetCode-44-通配符匹配

LeetCode-44-通配符匹配

44. 通配符匹配

相关推荐

一个分享Java & Python知识的社区