資訊專欄INFORMATION COLUMN
摘要：各一個指針，表示上一次真正到的位置。在的時候，上，增加下一步知道出界，發(fā)現(xiàn)是錯誤的所以需要回到上次的地方，即一旦走出去，無法返回，需要一個指針記錄最后的地方。
public class Solution {
public boolean isMatch(String s, String p) {
int idxs = 0, idxp = 0, idxmatch = 0, idxstar = -1;
// s, p 各一個指針， idxmatch表示s上一次真正match到的位置。
// abgefg *g
// 在idxs = 2的時候，match上，idxs增加
// 下一步知道p出界，發(fā)現(xiàn)是錯誤的match, 所以需要回到上次match的地方，即idxmatch
// ab ?*b
// aab ?*b
// bab b*b
while(idxs < s.length()){
if(idxp< p.length() && (p.charAt(idxp) == "?" || s.charAt(idxs) == p.charAt(idxp)) ) {
idxs++; // idxs一旦走出去，無法返回，需要一個指針記錄最后match的地方。
idxp++; // match錯誤，idxp可以由idxstar+1重新得到
} else if(idxp< p.length() && (p.charAt(idxp) == "*")) {
idxmatch = idxs; // 開始match的地方，idxs之前的必須完全match
idxstar = idxp; // 記錄*的位置
idxp++; // 嘗試match 0 個，即idxs不動，idxp往后移
} else if(idxstar != -1) { // 上次match錯誤，或者match不夠
idxmatch++; // idxmatch唯一標(biāo)記上次match的地方
idxs = idxmatch; // match
idxp = idxstar + 1; // 一次match一個
} else {
return false;
}
}
while(idxp< p.length() && p.charAt(idxp) == "*") { // trailing "*"s
idxp++;
}
return idxp == p.length();
}
}
public class Solution {
public boolean isMatch(String s, String p) {
boolean[][] match=new boolean[s.length()+1][p.length()+1];
match[s.length()][p.length()]=true;
for(int i=p.length()-1;i>=0;i--){
if(p.charAt(i)!="*")
break;
else
match[s.length()][i]=true;
}
for(int i=s.length()-1;i>=0;i--){
for(int j=p.length()-1;j>=0;j--){
if(s.charAt(i)==p.charAt(j)||p.charAt(j)=="?")
match[i][j]=match[i+1][j+1];
else if(p.charAt(j)=="*")
// i+1, j 表示j維持原位置，i向后一位，"*" match with s.charAt(i)
// i, j+1 表示i維持原位置，j向后一位，"*" match with ""(empty)
match[i][j]=match[i+1][j]||match[i][j+1];
else
match[i][j]=false;
}
}
return match[0][0];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/66537.html
摘要：正則由于的存在，所以有多種狀態(tài)，中間狀態(tài)儲存都需要記錄下來。然后以這些狀態(tài)為動態(tài)的中轉(zhuǎn)，繼續(xù)判斷到最后。最后正則匹配字符串是否成功的判斷依據(jù)，就是正則字符串的最大，是否出現(xiàn)在遍歷到最后的狀態(tài)列表中。 題目闡釋： 正則匹配字符串，用程序?qū)崿F(xiàn) 關(guān)鍵理解： 正則匹配，動態(tài)規(guī)劃思想，一個個向后追溯，后面的依賴前面的匹配成功。 正則和待匹配的字符串長度不一，統(tǒng)一到正則字符串的index索引上，每...
摘要：難度題目給出一個字符串和一個要求我們給出這個字符串是否匹配這個其中通配符跟我們平常見到的一樣是和代表任意單個字符代表一個或多個字符這個題跟簡單正則匹配比較類似可以跟這里面第二個解法一樣采取類似的動態(tài)規(guī)劃解法在里取中間某個確定的字符串序列將字 Implement wildcard pattern matching with support for ? and *. ? Matches ...
摘要：遞歸和動規(guī)的方法沒有研究，說一下較為直觀的貪心算法。用和兩個指針分別標(biāo)記和進行比較的位置，當(dāng)遍歷完后，若也遍歷完，說明完全配對。當(dāng)之前出現(xiàn)過，且此時和完全無法配對的時候，就一起退回在和配對過的位置。再將和逐個加繼續(xù)比較，并將后移。 Problem Implement wildcard pattern matching with support for ? and *. ? Matche...
摘要：當(dāng)我們遇到一個時，因為之后可能要退回至該位置重新匹配，我們要將它的下標(biāo)記錄下來，比如。但是，當(dāng)我們連續(xù)遇到兩次的情況，如何保證我還是能繼續(xù)匹配，而不是每次都退回導(dǎo)致循環(huán)呢所以我們還要記錄一個，用來記錄用上一個連續(xù)匹配到的中的下標(biāo)。 Wildcard Matching Implement wildcard pattern matching with support for ? and ...
摘要：題目鏈接這道題還是可以用的方法，用的數(shù)組來解，空間復(fù)雜度較高。和不同，這道題的符號和前面的沒有關(guān)系，不需要一起考慮。最壞的情況下，間隔出現(xiàn)且每個都要匹配很多字符，設(shè)一個平均匹配里面?zhèn)€字符，。其中，是的長度，是的長度。 Wildcard Matching 題目鏈接：https://leetcode.com/problems...這道題還是可以用Regular Expression Mat...
閱讀 1487·2019-08-30 15:44
閱讀 1952·2019-08-30 14:07
閱讀 2879·2019-08-30 13:56
閱讀 2347·2019-08-29 17:06
閱讀 1330·2019-08-29 14:13
閱讀 2088·2019-08-29 11:28
閱讀 3233·2019-08-26 13:56
閱讀 1953·2019-08-26 12:11
