給定一個字元串 (s) 和一個字元模式 § ,實作一個支援 ‘?’ 和 ‘*’ 的通配符比對。
‘?’ 可以比對任何單個字元。
‘*’ 可以比對任意字元串(包括空字元串)。
兩個字元串完全比對才算比對成功。
說明:
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 = “ab”
輸出: true
解釋: 第一個 ‘’ 可以比對空字元串, 第二個 '’ 可以比對字元串 “dce”.
示例 5:
輸入:
s = “acdcb”
p = “a*c?b”
輸出: false
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/wildcard-matching
解題思路
采用動态規劃, 用一個二維布爾數組,
boolean[][] dp = new boolean[sLen + 1][pLen + 1]
長度為什麼要是字元串長度 + 1? 是為了将字元為空這一情況也算進去
dp[i][j]
表示字元前 i 個和比對模式前 j 個是否比對成功
邊界條件
-
表示空字元比對空字元, 恒為真dp[0][0]
-
表示p為空, 固定為falsedp[i][0]
-
表示s為空, dp[0][j]當 p 前 j 個字元為 * 時為 truedp[0][j]
開始填寫二維數組
- 如果此時p是通配符, 則可以選擇忽略通配符 dp[i][j - 1], 或者不忽略通配符 dp[i - 1][j]
dp[i][j] = dp[i][j - 1] || dp[i - 1][j]
- 如果
或s[i] == p[j]
也就是目前p[j] == '?'
和s[i]
比對一定成功, 隻需要看前面的結果p[j]
dp[i][j] = dp[i - 1][j - 1]
最後傳回
dp[sLen][pLen]
代碼
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length();
int pLen = p.length();
// 數組長度為字元長度 + 1是為了将字元為空這一情況也算進去
// 也即dp[i][0]表示p為空, dp[0][j]表示s為空
// dp[i][0]固定為 false, dp[0][j]當p前j個字元為 * 時為 true
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
// dp[0][0]表示空字元比對空字元
dp[0][0] = true;
for (int i = 1; i <= pLen; i++) {
if (p.charAt(i - 1) == '*') {
dp[0][i] = true;
} else {
break;
}
}
for (int i = 1; i <= sLen; i++) {
for (int j = 1; j <= pLen; j++) {
// 如果此時p是通配符
if (p.charAt(j - 1) == '*') {
// 則可以選擇忽略通配符 dp[i][j - 1]
// 或者不忽略通配符 dp[i - 1][j]
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}
// 如果s[i] == p[j]或p[j] == '?'
else if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
// 也就是目前s[i]和p[j]比對一定成功, 隻需要看前面的結果
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[sLen][pLen];
}
}