[Leetcode] Wildcard Matching 通配符匹配

tainzhi 發布于2019-08-14 12:35 / 2112人閱讀

摘要：當我們遇到一個時，因為之后可能要退回至該位置重新匹配，我們要將它的下標記錄下來，比如。但是，當我們連續遇到兩次的情況，如何保證我還是能繼續匹配，而不是每次都退回導致循環呢所以我們還要記錄一個，用來記錄用上一個連續匹配到的中的下標。

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

雙指針法 復雜度

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

思路

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

s的字符和p的字符相等

p中的字符是?，這時無論s的字符是什么都可以匹配一個

p中遇到了一個*，這時無論s的字符是什么都沒關系

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

s已經匹配完，但是p后面還有很多連續的`*

這里1和2的情況比較好處理，關鍵在于如何處理3和4的情況。當我們遇到一個*時，因為之后可能要退回至該位置重新匹配，我們要將它的下標記錄下來，比如idxstar。但是，當我們連續遇到兩次4的情況，如何保證我還是能繼續匹配s，而不是每次都退回idxstar+1導致循環呢？所以我們還要記錄一個idxmatch，用來記錄用上一個*連續匹配到的s中的下標。最后，對于情況5，我們用一個循環跳過末尾的*跳過就行了。

代碼

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

GPU云服務器云服務器字符串通配符匹配算法 Wildcard matching LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64568.html

Leetcode 44 Wildcard Matching 通配符匹配

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

SimonMa 2019-08-14 17:16 評論0 收藏0
leetcode-44. Wildcard Matching

摘要：正則由于的存在，所以有多種狀態，中間狀態儲存都需要記錄下來。然后以這些狀態為動態的中轉，繼續判斷到最后。最后正則匹配字符串是否成功的判斷依據，就是正則字符串的最大，是否出現在遍歷到最后的狀態列表中。題目闡釋：正則匹配字符串，用程序實現關鍵理解：正則匹配，動態規劃思想，一個個向后追溯，后面的依賴前面的匹配成功。正則和待匹配的字符串長度不一，統一到正則字符串的index索引上，每...

leanxi 2019-07-30 17:20 評論0 收藏0
Wildcard Matching

摘要：題目鏈接這道題還是可以用的方法，用的數組來解，空間復雜度較高。和不同，這道題的符號和前面的沒有關系，不需要一起考慮。最壞的情況下，間隔出現且每個都要匹配很多字符，設一個平均匹配里面個字符，。其中，是的長度，是的長度。 Wildcard Matching 題目鏈接：https://leetcode.com/problems...這道題還是可以用Regular Expression Mat...

galaxy_robot 2019-08-14 17:19 評論0 收藏0
[LintCode/LeetCode] Wildcard Matching

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

Ethan815 2019-08-14 15:43 評論0 收藏0
Nginx基本知識點

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

jzzlee 2019-07-25 14:12 評論0 收藏0