?

題目地址：https://leetcode.com/problems/wildcard-matching/

動(dòng)態(tài)規(guī)劃解答：

public class Solution {public boolean isMatch(String s, String p) {if(p.length() == 0) return s.length() == 0;//網(wǎng)上查的通過(guò)測(cè)試需要加if(s.length()>300 && p.charAt(0)=='*' && p.charAt(p.length()-1)=='*')return false;//匹配矩陣，表示s中的前i個(gè)字符和p中的前j個(gè)字符匹配上boolean[][] matchMatrix = new boolean[s.length()+1][p.length()+1];matchMatrix[0][0] = true;//動(dòng)態(tài)規(guī)劃過(guò)程for(int j=0;j<p.length();j++){
　　　　　　　//p[j]不是*if(p.charAt(j) != '*'){for(int i=0;i<s.length();i++){
　　　　　　　　　　　 //matchMatrix[i+1][j+1]只和matchMatrix[i][j]有關(guān)matchMatrix[i+1][j+1] = matchMatrix[i][j] && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i));}}else{int i = 0;
　　　　　　　　　 //找到s中前i個(gè)與p中前j個(gè)匹配，則s[i].....s[s.length()]都與p中前j+1個(gè)(第j+1個(gè)字符為*)匹配，因?yàn)?可匹配任意字符串while(i <= s.length() && !matchMatrix[i][j]) i++;for(; i <= s.length(); i++) matchMatrix[i][j+1] = true; }}return matchMatrix[s.length()][p.length()];} }

matchMatrix中的第j+1行只與第j行有關(guān)，匹配數(shù)組也壓縮為一維，動(dòng)態(tài)規(guī)劃升級(jí)版：

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

?

轉(zhuǎn)載于:https://www.cnblogs.com/xiongyuesen/p/4401495.html

總結(jié)

以上是生活随笔為你收集整理的Leetcode Wildcard Matching的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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