通配符匹配

給定一個字符串 (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

對比與leetcode10區(qū)別
首先星號可以匹配任何字符串，這個與10不同，那個星號前面必然有字母，就會造成在初始化時，數(shù)組越界

這種依然是可以匹配的，所以這里的星號與10題作用是不同的，這里是不需要有字母，星號可以表示任何字母，或者0個字母，也就是自己消失，所以就不需要參照星號之前字符的類型，轉(zhuǎn)變?yōu)楫嫳砀?#xff0c;參照左前，左上，正上三個狀態(tài)即可
表格參照教程
注意這里的i,j是相反的

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;//初始化第一列，即s為空字符串，初始化方式也不再相同for(int i = 1; i<= n; i++){dp[0][i] = dp[0][i - 1] && p.charAt(i - 1) == '*';}for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(s.charAt(i - 1) == p.charAt(j - 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] || dp[i - 1][j - 1];//i控制行數(shù)，j控制列數(shù)//dp[i][j - 1]就是左前方，*對應(yīng)多個//dp[i - 1][j]對應(yīng)正上方，*對應(yīng)為0個//dp[i - 1][j - 1]對應(yīng)對角線斜上方，就是*當(dāng)做一個}}}return dp[m][n];} }

總結(jié)

以上是生活随笔為你收集整理的L44. 通配符匹配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。