成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

LC44 wildcard matching

Tychio / 3140人閱讀

摘要：各一個(gè)指針，表示上一次真正到的位置。在的時(shí)候，上，增加下一步知道出界，發(fā)現(xiàn)是錯(cuò)誤的所以需要回到上次的地方，即一旦走出去，無(wú)法返回，需要一個(gè)指針記錄最后的地方。

public class Solution {
    public boolean isMatch(String s, String p) {
        int idxs = 0, idxp = 0, idxmatch = 0, idxstar = -1;
        // s, p 各一個(gè)指針，   idxmatch表示s上一次真正match到的位置。
        // abgefg             *g
        // 在idxs = 2的時(shí)候，match上，idxs增加
        // 下一步知道p出界，發(fā)現(xiàn)是錯(cuò)誤的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一旦走出去，無(wú)法返回，需要一個(gè)指針記錄最后match的地方。
                idxp++;                 // match錯(cuò)誤，idxp可以由idxstar+1重新得到
            } else if(idxp< p.length() && (p.charAt(idxp) == "*")) {
                idxmatch = idxs;        // 開(kāi)始match的地方，idxs之前的必須完全match
                idxstar = idxp;         // 記錄*的位置
                idxp++;                 // 嘗試match 0 個(gè)，即idxs不動(dòng)，idxp往后移
            } else if(idxstar != -1) {  // 上次match錯(cuò)誤，或者match不夠
                idxmatch++;             // idxmatch唯一標(biāo)記上次match的地方 
                idxs = idxmatch;        // match
                idxp = idxstar + 1;     // 一次match一個(gè)
            } 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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66537.html

相關(guān)文章

  • leetcode-44. Wildcard Matching

    摘要：正則由于的存在，所以有多種狀態(tài)，中間狀態(tài)儲(chǔ)存都需要記錄下來(lái)。然后以這些狀態(tài)為動(dòng)態(tài)的中轉(zhuǎn)，繼續(xù)判斷到最后。最后正則匹配字符串是否成功的判斷依據(jù)，就是正則字符串的最大，是否出現(xiàn)在遍歷到最后的狀態(tài)列表中。 題目闡釋?zhuān)?正則匹配字符串，用程序?qū)崿F(xiàn) 關(guān)鍵理解： 正則匹配，動(dòng)態(tài)規(guī)劃思想，一個(gè)個(gè)向后追溯，后面的依賴(lài)前面的匹配成功。 正則和待匹配的字符串長(zhǎng)度不一，統(tǒng)一到正則字符串的index索引上，每...

    leanxi 評(píng)論0 收藏0

  • Leetcode 44 Wildcard Matching 通配符匹配

    摘要：難度題目給出一個(gè)字符串和一個(gè)要求我們給出這個(gè)字符串是否匹配這個(gè)其中通配符跟我們平常見(jiàn)到的一樣是和代表任意單個(gè)字符代表一個(gè)或多個(gè)字符這個(gè)題跟簡(jiǎn)單正則匹配比較類(lèi)似可以跟這里面第二個(gè)解法一樣采取類(lèi)似的動(dòng)態(tài)規(guī)劃解法在里取中間某個(gè)確定的字符串序列將字 Implement wildcard pattern matching with support for ? and *. ? Matches ...

    SimonMa 評(píng)論0 收藏0

  • [LintCode/LeetCode] Wildcard Matching

    摘要：遞歸和動(dòng)規(guī)的方法沒(méi)有研究，說(shuō)一下較為直觀(guān)的貪心算法。用和兩個(gè)指針?lè)謩e標(biāo)記和進(jìn)行比較的位置，當(dāng)遍歷完后，若也遍歷完，說(shuō)明完全配對(duì)。當(dāng)之前出現(xiàn)過(guò)，且此時(shí)和完全無(wú)法配對(duì)的時(shí)候，就一起退回在和配對(duì)過(guò)的位置。再將和逐個(gè)加繼續(xù)比較，并將后移。 Problem Implement wildcard pattern matching with support for ? and *. ? Matche...

    Ethan815 評(píng)論0 收藏0

  • [Leetcode] Wildcard Matching 通配符匹配

    摘要：當(dāng)我們遇到一個(gè)時(shí)，因?yàn)橹罂赡芤嘶刂猎撐恢弥匦缕ヅ?，我們要將它的下?biāo)記錄下來(lái)，比如。但是，當(dāng)我們連續(xù)遇到兩次的情況，如何保證我還是能繼續(xù)匹配，而不是每次都退回導(dǎo)致循環(huán)呢所以我們還要記錄一個(gè)，用來(lái)記錄用上一個(gè)連續(xù)匹配到的中的下標(biāo)。 Wildcard Matching Implement wildcard pattern matching with support for ? and ...

    tainzhi 評(píng)論0 收藏0

  • Wildcard Matching

    摘要：題目鏈接這道題還是可以用的方法，用的數(shù)組來(lái)解，空間復(fù)雜度較高。和不同，這道題的符號(hào)和前面的沒(méi)有關(guān)系，不需要一起考慮。最壞的情況下，間隔出現(xiàn)且每個(gè)都要匹配很多字符，設(shè)一個(gè)平均匹配里面?zhèn)€字符，。其中，是的長(zhǎng)度，是的長(zhǎng)度。 Wildcard Matching 題目鏈接：https://leetcode.com/problems...這道題還是可以用Regular Expression Mat...

    galaxy_robot 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<