44. 通配符匹配

题目描述

输入字符串 s 和模式串 p，实现通配符匹配。p 中可以出现两种通配符：

'?' 对应任意一个字符；'*' 对应任意长度的一串字符，长度可以是 0。其他字符只能对应和自己相同的字符。

只有 p 能从头到尾对应整个 s 时才算匹配。匹配返回 true，否则返回 false。

示例 1

输入：s = "aa", p = "a"
输出：false

解释："a" 只对应一个字符，覆盖不了 "aa"。

示例 2

输入：s = "aa", p = "*"
输出：true

解释：'*' 可以对应任何字符串。

示例 3

输入：s = "cb", p = "?a"
输出：false

解释：'?' 对应 'c'，但 'a' 与 'b' 不同。

数据范围

0 <= s.length, p.length <= 2000
s 只含小写英文字母。
p 只含小写英文字母、'?' 和 '*'。

解题思路

设 dp[i][j] 表示 s 的前 i 个字符能否被 p 的前 j 个字符匹配。如果 p[j-1] 是 ? 或者和 s[i-1] 相同，就看左上格 dp[i-1][j-1]。如果是 *，它要么匹配空串（看左边格 dp[i][j-1]），要么多吃掉 s[i-1] 并继续保留（看上面格 dp[i-1][j]）。第 0 行只有前缀全是 * 时才是 True。

为什么正确

按行从左到右填表时，左、上、左上三格都已经算好。

复杂度分析

时间 O(mn)，空间 O(mn)。

易错点

忘记初始化第 0 行：s 为空时，p="**" 也能匹配。只要遇到第一个非 * 字符，之后的 dp[0][j] 都是 False。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j - 1] and p[j - 1] == '*'
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
                elif p[j - 1] in (s[i - 1], '?'):
                    dp[i][j] = dp[i - 1][j - 1]
        return dp[m][n]

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] && p.charAt(j - 1) == '*';
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] && p[j - 1] == '*';
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (p[j - 1] == s[i - 1] || p[j - 1] == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

func isMatch(s string, p string) bool {
	m, n := len(s), len(p)
	dp := make([][]bool, m+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true
	for j := 1; j <= n; j++ {
		dp[0][j] = dp[0][j-1] && p[j-1] == '*'
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p[j-1] == '*' {
				dp[i][j] = dp[i][j-1] || dp[i-1][j]
			} else if p[j-1] == s[i-1] || p[j-1] == '?' {
				dp[i][j] = dp[i-1][j-1]
			}
		}
	}
	return dp[m][n]
}

var isMatch = function(s, p) {
    const m = s.length, n = p.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
    dp[0][0] = true;
    for (let j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j - 1] && p[j - 1] === '*';
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            } else if (p[j - 1] === s[i - 1] || p[j - 1] === '?') {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
};

function isMatch(s: string, p: string): boolean {
    const m = s.length, n = p.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
    dp[0][0] = true;
    for (let j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j - 1] && p[j - 1] === '*';
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            } else if (p[j - 1] === s[i - 1] || p[j - 1] === '?') {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
}

载入编辑器，自己跑一遍 →

其他解法

动态规划枚举所有前缀对，思路系统、容易推广；贪心利用星号可匹配任意串的性质，只回退到最近的星号，把空间降到 O(1)。

解法 2：贪心 + 回退到最近的星号时间 O(mn)，空间 O(1)

用 i、j 分别扫描 s 和 p。字符相等或遇到 '?' 时两者同时前进；遇到 '*' 时记下星号位置 star 和此时 s 的位置 match，先让星号匹配空串。之后若失配且出现过星号，就让最近的星号多吞一个字符：match 加一，i 回到 match，j 回到 star+1。s 扫完后，p 剩余部分必须全是 '*'。

只用常数空间，实际数据上通常接近线性，最坏情况仍是 O(mn)。正确性依赖一个关键观察：遇到新星号后，更早的星号无需再调整，因此只回退到最近的星号即可。证明比动态规划难，但代码短、内存省。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        i = j = 0
        star, match = -1, 0
        while i < m:
            if j < n and (p[j] == s[i] or p[j] == '?'):
                i += 1
                j += 1
            elif j < n and p[j] == '*':
                star, match = j, i
                j += 1
            elif star != -1:
                match += 1
                i, j = match, star + 1
            else:
                return False
        while j < n and p[j] == '*':
            j += 1
        return j == n

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        int i = 0, j = 0, star = -1, match = 0;
        while (i < m) {
            if (j < n && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')) {
                i++; j++;
            } else if (j < n && p.charAt(j) == '*') {
                star = j; match = i; j++;
            } else if (star != -1) {
                match++; i = match; j = star + 1;
            } else {
                return false;
            }
        }
        while (j < n && p.charAt(j) == '*') j++;
        return j == n;
    }
}

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        int i = 0, j = 0, star = -1, match = 0;
        while (i < m) {
            if (j < n && (p[j] == s[i] || p[j] == '?')) {
                i++; j++;
            } else if (j < n && p[j] == '*') {
                star = j; match = i; j++;
            } else if (star != -1) {
                match++; i = match; j = star + 1;
            } else {
                return false;
            }
        }
        while (j < n && p[j] == '*') j++;
        return j == n;
    }
};

func isMatch(s string, p string) bool {
	m, n := len(s), len(p)
	i, j, star, match := 0, 0, -1, 0
	for i < m {
		if j < n && (p[j] == s[i] || p[j] == '?') {
			i++
			j++
		} else if j < n && p[j] == '*' {
			star, match = j, i
			j++
		} else if star != -1 {
			match++
			i, j = match, star+1
		} else {
			return false
		}
	}
	for j < n && p[j] == '*' {
		j++
	}
	return j == n
}

var isMatch = function(s, p) {
    const m = s.length, n = p.length;
    let i = 0, j = 0, star = -1, match = 0;
    while (i < m) {
        if (j < n && (p[j] === s[i] || p[j] === '?')) {
            i++; j++;
        } else if (j < n && p[j] === '*') {
            star = j; match = i; j++;
        } else if (star !== -1) {
            match++; i = match; j = star + 1;
        } else {
            return false;
        }
    }
    while (j < n && p[j] === '*') j++;
    return j === n;
};

function isMatch(s: string, p: string): boolean {
    const m = s.length, n = p.length;
    let i = 0, j = 0, star = -1, match = 0;
    while (i < m) {
        if (j < n && (p[j] === s[i] || p[j] === '?')) {
            i++; j++;
        } else if (j < n && p[j] === '*') {
            star = j; match = i; j++;
        } else if (star !== -1) {
            match++; i = match; j = star + 1;
        } else {
            return false;
        }
    }
    while (j < n && p[j] === '*') j++;
    return j === n;
}

动态规划专题的其他题目

查看动态规划全部题目 →