Wildcard Matching -- LeetCode

 
這道題目其實是Regular Expression Matching的簡化版，在這裡'?'相當於那邊的'.'，而'*'相當於那邊的'.*'，因為這裡'*'就可以代替任何字符串，不需要看前面的字符，所以處理起來更加簡單。
brute force的方法就不重新列舉代碼了，有興趣實現的朋友可以參考一下Regular Expression Matching，代碼結構一樣，只是處理情況變一下就可以，不過leetcode過不了（因為超時）。
我們主要還是說一下動態規劃的方法。跟Regular Expression Matching一樣，還是維護一個假設我們維護一個布爾數組res[i],代表s的前i個字符和p的前j個字符是否匹配(這裡因為每次i的結果只依賴於j-1的結果，所以不需要二維數組，只需要一個一維數組來保存上一行結果即可），遞推公式分兩種情況：
(1)p[j]不是'*'。情況比較簡單，只要判斷如果當前s的i和p的j上的字符一樣（如果有p在j上的字符是'?'，也是相同），並且res[i]==true，則更新res[i+1]為true，否則res[i+1]=false;
(2)p[j]是'*'。因為'*'可以匹配任意字符串，所以在前面的res[i]只要有true，那麼剩下的 res[i+1], res[i+2],...,res[s.length()]就都是true了。
算法的時間復雜度因為是兩層循環，所以是O(m*n), 而空間復雜度只用一個一維數組，所以是O(n)，假設s的長度是n，p的長度是m。代碼如下：

public boolean isMatch(String s, String p) {
    if(p.length()==0)
        return s.length()==0;
    boolean[] res = new boolean[s.length()+1];
    res[0] = true;
    for(int j=0;j=0;i--)
            {
                res[i+1] = res[i]&&(p.charAt(j)=='?'||s.charAt(i)==p.charAt(j));
            }
        }
        else
        {
            int i = 0;
            while(i<=s.length() && !res[i])
                i++;
            for(;i<=s.length();i++)
            {
                res[i] = true;
            }
        }
        res[0] = res[0]&&p.charAt(j)=='*';
    }
    return res[s.length()];
}

這裡有個問題，就是如果把以上代碼直接放到LeetCode中去測試，會有最後一個test case過不了，說超時了，這道題的AC率這麼低就是因為這個case，從難度來說，這個題比Regular Expression Matching簡單一些。個人覺得這其實是LeetCode的問題，把測試超時的檻設得太低了，好像用C++就能過，因為效率比較高，而java可能要摳各種細節，這其實意義不是很大，既然算法復雜度已經到位了，就應該可以過，甚至覺得時間應該設得更高一些，連同brute force也讓過，這樣方便大家測試一道題的不同解法，至少檢驗正確性，時間上大家自己去分析就可以。所以如果想要過最後一個case可以在代碼的第一個if以後加上以下兩行跳過那個case：

if(s.length()>300 && p.charAt(0)=='*' && p.charAt(p.length()-1)=='*')
    return false;

這種模糊匹配的題目是面試中的一類題目，一般在onsite的時候會遇到，如果沒有熟悉思路有時候當場可能很難做得很好。