国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Wildcard Matching 通配符匹配

tainzhi / 2103人閱讀

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

Wildcard Matching 
Implement wildcard pattern matching with support for "?" and "*".


"?" Matches any single character. "*" Matches any sequence of characters (including the empty sequence).


The matching should cover the entire input string (not partial).


The function prototype should be: bool isMatch(const char *s, const char *p)


Some examples:


isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
雙指針法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

假設(shè)我們用兩個(gè)指針分別指向s和p字符串中要匹配的位置，首先分析下通配符匹配過程中會(huì)有哪些情況是成功：

s的字符和p的字符相等

p中的字符是?，這時(shí)無論s的字符是什么都可以匹配一個(gè)

p中遇到了一個(gè)*，這時(shí)無論s的字符是什么都沒關(guān)系

之前的都不符合，但是p在之前的位置有一個(gè)*，我們可以從上一個(gè)*后面開始匹配

s已經(jīng)匹配完，但是p后面還有很多連續(xù)的`*

這里1和2的情況比較好處理，關(guān)鍵在于如何處理3和4的情況。當(dāng)我們遇到一個(gè)*時(shí)，因?yàn)橹罂赡芤嘶刂猎撐恢弥匦缕ヅ洌覀円獙⑺南聵?biāo)記錄下來，比如idxstar。但是，當(dāng)我們連續(xù)遇到兩次4的情況，如何保證我還是能繼續(xù)匹配s，而不是每次都退回idxstar+1導(dǎo)致循環(huán)呢？所以我們還要記錄一個(gè)idxmatch，用來記錄用上一個(gè)*連續(xù)匹配到的s中的下標(biāo)。最后，對(duì)于情況5，我們用一個(gè)循環(huán)跳過末尾的*跳過就行了。

代碼 
public class Solution {
    public boolean isMatch(String s, String p) {
        int idxs = 0, idxp = 0, idxstar = -1, idxmatch = 0;
        while(idxs < s.length()){
            // 當(dāng)兩個(gè)指針指向完全相同的字符時(shí)，或者p中遇到的是?時(shí)
            if(idxp < p.length() && (s.charAt(idxs) == p.charAt(idxp) || p.charAt(idxp) == "?")){
                idxp++;
                idxs++;
            // 如果字符不同也沒有?，但在p中遇到是*時(shí)，我們記錄下*的位置，但不改變s的指針
            } else if(idxp < p.length() && p.charAt(idxp)=="*"){
                idxstar = idxp;
                idxp++;
                //遇到*后，我們用idxmatch來記錄*匹配到的s字符串的位置，和不用*匹配到的s字符串位置相區(qū)分
                idxmatch = idxs;
            // 如果字符不同也沒有?，p指向的也不是*，但之前已經(jīng)遇到*的話，我們可以從idxmatch繼續(xù)匹配任意字符
            } else if(idxstar != -1){
                // 用上一個(gè)*來匹配，那我們p的指針也應(yīng)該退回至上一個(gè)*的后面
                idxp = idxstar + 1;
                // 用*匹配到的位置遞增
                idxmatch++;
                // s的指針退回至用*匹配到位置
                idxs = idxmatch;
            } else {
                return false;
            }
        }
        // 因?yàn)?個(gè)*能匹配無限序列，如果p末尾有多個(gè)*，我們都要跳過
        while(idxp < p.length() && p.charAt(idxp) == "*"){
            idxp++;
        }
        // 如果p匹配完了，說明匹配成功
        return idxp == p.length();
    }
}

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

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

相關(guān)文章

  • Leetcode 44 Wildcard Matching 通配符匹配

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

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

  • leetcode-44. Wildcard Matching

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

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

  • Wildcard Matching

    摘要：題目鏈接這道題還是可以用的方法，用的數(shù)組來解，空間復(fù)雜度較高。和不同，這道題的符號(hào)和前面的沒有關(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

  • [LintCode/LeetCode] Wildcard Matching

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

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

  • Nginx基本知識(shí)點(diǎn)

    摘要：基本的體系結(jié)構(gòu)由進(jìn)程和其進(jìn)程組成。讀取配置文件，并維護(hù)進(jìn)程，而則會(huì)對(duì)請(qǐng)求進(jìn)行實(shí)際處理。普通指令在每個(gè)上下文僅有唯一值。最小化配置有了這些知識(shí)我們應(yīng)該能夠創(chuàng)建并理解運(yùn)行所需的最低配置。 什么是 Nginx？ Nginx 最初是作為一個(gè) Web 服務(wù)器創(chuàng)建的，用于解決 C10k 的問題。作為一個(gè) Web 服務(wù)器，它可以以驚人的速度為您的數(shù)據(jù)服務(wù)。但 Nginx 不僅僅是一個(gè) Web 服務(wù)器...

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

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

0條評(píng)論

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