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

資訊專(zhuān)欄INFORMATION COLUMN

Wildcard Matching

galaxy_robot / 2435人閱讀

摘要：題目鏈接這道題還是可以用的方法，用的數(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 Matching" 的方法，用2d的dp數(shù)組來(lái)解，空間復(fù)雜度較高。

    public boolean isMatch(String s, String p) {
        /* boolean dp[len(s) + 1][len(p) + 1] 
         * dp[i+1][j+1] means if s[0, i] match p[0, j]
         * function: dp[i+1][j+1] 
         *         a. p[j] = * => 1. empty: dp[i+1][j]
         *                        2. one: dp[i][j]
         *                        3. multiple: dp[i][j+1]
         *         b. p[j] = s[i] | p[j] = ? => dp[i][j]
         * start: dp[0][0] = true, dp[0][j+1] = dp[0][j] & p[j] = *
         * result: dp[len(s)][len(p)]
         */
         
         boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
         // start
         dp[0][0] = true;
         for(int j = 0; j < p.length(); j++) dp[0][j+1] = dp[0][j] & (p.charAt(j) == "*");
         
         // loop
         for(int i = 0; i < s.length(); i++) {
             for(int j = 0; j < p.length(); j++) {
                 if(p.charAt(j) == "*") {
                     dp[i+1][j+1] = dp[i+1][j] | dp[i][j] | dp[i][j+1];
                 }
                 else if(p.charAt(j) == s.charAt(i) || p.charAt(j) == "?") dp[i+1][j+1] = dp[i][j];
             }
         }
         return dp[s.length()][p.length()];
    }

另一種思路是greedy，只需要O(1)的空間。和regular expression不同，這道題的star符號(hào)和前面的character沒(méi)有關(guān)系，不需要一起考慮。而且star是可以匹配任何string的，"aa", "ab"都可以。所以check是否匹配的時(shí)候，只需要按位一個(gè)一個(gè)判斷就行了。用兩個(gè)指針i和j分別掃描s和p，loop過(guò)程中有以下幾種情況：

成功匹配：s[i] == p[j] or p[j] == "?" => i++, j++

出現(xiàn)星號(hào)：p[j] == "*"

匹配不上：return false

第二種情況比較麻煩，多帶帶討論一下。

p[j]匹配0個(gè) => j++

p[j]匹配1個(gè) => j++, i += 1

p[j]匹配2個(gè) => j++, i += 2
......

可以看出來(lái)，要嘗試不同的匹配個(gè)數(shù)，所以要加兩個(gè)指針保存之前出現(xiàn)star時(shí)的i和j：stari和starj。那么每次碰到"*"的時(shí)候，都保存一下，先試下匹配0個(gè)的時(shí)候后面的字符是否可以匹配上，如果不行再試1個(gè)，2個(gè)。。重復(fù)這個(gè)過(guò)程。
以s的長(zhǎng)度為loop的終點(diǎn)，所以最后還要考慮一下p后面還有多的"*"的情況。

時(shí)間復(fù)雜度度

最好的情況下，沒(méi)有star或者所有star都匹配0個(gè)字符，O(M+N)。
最壞的情況下，star間隔出現(xiàn)且每個(gè)star都要匹配很多字符，設(shè)一個(gè)star平均匹配s里面x個(gè)字符，O(xN + M) = O(M*N)。其中，M是s的長(zhǎng)度，N是p的長(zhǎng)度。

    public boolean isMatch(String s, String p) {
        int i = 0, j = 0;
        int stari = -1, starj = -1;
        while(i < s.length()) {
            // 1. match
            if(j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == "?")) {
                i++; j++;
            }
            // 2. star
            else if(j < p.length() && p.charAt(j) == "*") {
                // first match 0
                stari = i;
                starj = ++j;
            }
            // different number that "*" matches 
            else if(stari != -1) {
                // match number +1
                i = ++stari;
                j = starj;
            }
            // 3. not match and no star
            else return false;
        }
        // remove last "*" in p
        while(j < p.length() && p.charAt(j) == "*") j++;
        
        return j == p.length();
    }

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66562.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] 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

  • [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

  • LC44 wildcard matching

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

    Tychio 評(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

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

0條評(píng)論

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