[LintCode/LeetCode] Wildcard Matching

Ethan815 發(fā)布于2019-08-14 15:43 / 3266人閱讀

摘要：遞歸和動規(guī)的方法沒有研究，說一下較為直觀的貪心算法。用和兩個指針分別標記和進行比較的位置，當遍歷完后，若也遍歷完，說明完全配對。當之前出現(xiàn)過，且此時和完全無法配對的時候，就一起退回在和配對過的位置。再將和逐個加繼續(xù)比較，并將后移。

Problem

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).

Example

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

Note

遞歸和動規(guī)的方法沒有研究，說一下較為直觀的貪心算法。

用cs和cp兩個指針分別標記s和p進行比較的位置，當cs遍歷完s后，若cp也遍歷完p，說明完全配對。

我們看一下while循環(huán)里的幾個分支：

第一個if語句，若cp和cs指向的字符相等，或cp指向的字符為"?"，則說明這一位配對成功，兩個指針繼續(xù)前移；

第二個else if語句，當cp指向的字符為"*"，則后面字符的配對結果要受到影響，必須用star和match分別在p和s的當前位置，也就是cp和cs，進行標記。然后，cp前移，cs不動，為什么呢？因為，如果此時cp == p.length()，就已經可以結束while循環(huán)了；但若cp不是末位，那么p剩下的字符還要繼續(xù)判斷，至于cs，完全可以等到下一次成功配對字符后再移動；

第三個else if語句，這里最為費解。當p之前出現(xiàn)過star，且此時cp和cs完全無法配對的時候，就一起退回在star和match配對過的位置。再將cp和cs逐個加1繼續(xù)比較，并將match后移。為什么star不用后移呢？因為star是大BOSS，可以任意和后面match走過的很多位配對下去呀；

最后一個else語句，返回false。但是這個false包含了哪些情況呢？其實，就是p中沒有star且無法配對的情況。

再用一個while循環(huán)跳過p尾部的所有"*"，如果有的話。
最后，若cp走完p，說明完全配對。

Solution

Greedy

public class Solution {
    public boolean isMatch(String s, String p) {
        int cs = 0, cp = 0, star = -1, match = 0;
        while (cs < s.length()) {
            if (cp < p.length() && (p.charAt(cp) == s.charAt(cs) || p.charAt(cp) == "?")) {
                cs++;
                cp++;
            }
            else if (cp < p.length() && p.charAt(cp) == "*") {
                star = cp;
                match = cs;
                cp++;
            }
            else if (star != -1) {
                cp = star + 1;
                cs = match + 1;
                match++;
            }
            else return false;
        }
        while (cp < p.length() && p.charAt(cp) == "*") cp++;
        return cp == p.length();
    }
}

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;
        int lens = s.length();
        int lenp = p.length();
        boolean[][] dp = new boolean[lens + 1][lenp + 1];
        boolean flag = false;
        for (int i = 0; i <= lens; i++) {
            flag = false;
            for (int j = 0; j <= lenp; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                    flag = true;
                    continue;
                }
                if (j == 0) {
                    dp[i][j] = false;
                    continue;
                }
                if (i == 0) dp[i][j] = dp[i][j - 1] && p.charAt(j - 1) == "*";
                else dp[i][j] = (matchChar(s.charAt(i - 1), p.charAt(j - 1)) && dp[i - 1][j - 1]) 
                                || (p.charAt(j - 1) == "*" && (dp[i][j - 1] || dp[i - 1][j]));    
                if (dp[i][j]) flag = true;
                if (dp[i][j] && p.charAt(j - 1) == "*" && j == lenp) return true;
            }
            if (!flag) return false;
        }
        return dp[lens][lenp];
    }
    public static boolean matchChar(char c, char p) {
        return (p == "?" || p == c);
    }
}

GPU云服務器云服務器 Wildcard matching

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

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

leetcode-44. Wildcard Matching

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

leanxi 2019-07-30 17:20 評論0 收藏0
[Leetcode] Wildcard Matching 通配符匹配

摘要：當我們遇到一個時，因為之后可能要退回至該位置重新匹配，我們要將它的下標記錄下來，比如。但是，當我們連續(xù)遇到兩次的情況，如何保證我還是能繼續(xù)匹配，而不是每次都退回導致循環(huán)呢所以我們還要記錄一個，用來記錄用上一個連續(xù)匹配到的中的下標。 Wildcard Matching Implement wildcard pattern matching with support for ? and ...

tainzhi 2019-08-14 12:35 評論0 收藏0
Wildcard Matching

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

galaxy_robot 2019-08-14 17:19 評論0 收藏0
LC44 wildcard matching

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

Tychio 2019-08-14 17:17 評論0 收藏0
Leetcode 44 Wildcard Matching 通配符匹配

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

SimonMa 2019-08-14 17:16 評論0 收藏0