Wildcard Matching

galaxy_robot 發(fā)布于2019-08-14 17:19 / 2415人閱讀

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

Wildcard Matching

題目鏈接：
https://leetcode.com/problems...
這道題還是可以用"Regular Expression Matching" 的方法，用2d的dp數(shù)組來解，空間復雜度較高。

    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符號和前面的character沒有關(guān)系，不需要一起考慮。而且star是可以匹配任何string的，"aa", "ab"都可以。所以check是否匹配的時候，只需要按位一個一個判斷就行了。用兩個指針i和j分別掃描s和p，loop過程中有以下幾種情況：

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

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

匹配不上：return false

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

p[j]匹配0個 => j++

p[j]匹配1個 => j++, i += 1

p[j]匹配2個 => j++, i += 2
......

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

時間復雜度度

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

    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();
    }