Regular Expression Matching -- LeetCode

原題鏈接: http://oj.leetcode.com/problems/regular-expression-matching/
這個題目比較常見，但是難度還是比較大的。我們先來看看brute force怎麼解決。基本思路就是先看字符串s和p的從i和j開始的子串是否匹配，用遞歸的方法直到串的最後，最後回溯回來得到結果。假設現在走到s的i位置，p的j位置，情況分為下列兩種：
(1)p[j+1]不是'*'。情況比較簡單，只要判斷當前s的i和p的j上的字符是否一樣（如果有p在j上的字符是'.',也是相同），如果不同，返回false，否則，遞歸下一層i+1，j+1;
(2)p[j+1]是'*'。那麼此時看從s[i]開始的子串，假設s[i],s[i+1],...s[i+k]都等於p[j]那麼意味著這些都有可能是合適的匹配，那麼遞歸對於剩下的(i,j+2),(i+1,j+2),...,(i+k,j+2)都要嘗試（j+2是因為跳過當前和下一個'*'字符）。
實現代碼如下：

public boolean isMatch(String s, String p) {
    return helper(s,p,0,0);
}
private boolean helper(String s, String p, int i, int j)
{
    if(j==p.length())
        return i==s.length();
    
    if(j==p.length()-1 || p.charAt(j+1)!='*')
    {
        if(i==s.length()|| s.charAt(i)!=p.charAt(j) && p.charAt(j)!='.')
            return false;
        else
            return helper(s,p,i+1,j+1);
    }
    //p.charAt(j+1)=='*'
    while(i接下來我們考慮如何優化brute
 force算法，熟悉動態規劃的朋友可能發現了，其實這個思路已經很接近動態規劃了。動態規劃基本思想就是把我們計算過的歷史信息記錄下來，等到要用到的時候就直接使用，不用重新計算。在這個題裡面，假設我們維護一個布爾數組res[i][j],代表s的前i個字符和p的前j個字符是否匹配(注意這裡res的維度是s.length()+1,p.length()+1)。遞推公式跟上面類似，分三種種情況： 

(1)p[j+1]不是'*'。情況比較簡單，只要判斷如果當前s的i和p的j上的字符一樣（如果有p在j上的字符是'.',也是相同），並且res[i][j]==true，則res[i+1][j+1]也為true，res[i+1][j+1]=false; 

(2)p[j+1]是'*'，但是p[j]!='.'。那麼只要以下條件有一個滿足即可對res[i+1][j+1]賦值為true： 

    1)res[i+1][j]為真（'*'只取前面字符一次）; 

    2)res[i+1][j-1]為真（'*'前面字符一次都不取，也就是忽略這兩個字符）; 

    3)res[i][j+1] && s[i]==s[i-1] && s[i-1]==p[j-1](這種情況是相當於i從0到s.length()掃過來，如果p[j+1]對應的字符是‘*’那就意味著接下來的串就可以依次匹配下來，如果下面的字符一直重復，並且就是‘*’前面的那個字符）。 

(3)p[j+1]是'*'，並且p[j]=='.'。因為".*"可以匹配任意字符串，所以在前面的res[i+1][j-1]或者res[i+1][j]中只要有i+1是true，那麼剩下的res[i+1][j+1],res[i+2][j+1],...,res[s.length()][j+1]就都是true了。 

這道題有個很重要的點，就是實現的時候外層循環應該是p,然後待匹配串s內層循環掃過來。代碼如下： 
public boolean isMatch(String s, String p) {
    if(s.length()==0 && p.length()==0)
        return true;
    if(p.length()==0)
        return false;
    boolean[][] res = new boolean[s.length()+1][p.length()+1];
    res[0][0] = true;
    for(int j=0;j0 && res[0][j-1]) res[0][j+1]=true;
            if(j<1) continue;
            if(p.charAt(j-1)!='.')
            {
                for(int i=0;i0&&res[i+1][j-1] 
                    || i>0 && j>0 && res[i][j+1]&&s.charAt(i)==s.charAt(i-1)&&s.charAt(i-1)==p.charAt(j-1))
                        res[i+1][j+1] = true;
                }
            }
            else
            {
                int i=0;
                while(j>0 && i對比以上兩種做法，其實思路基本類似，動態規劃優勢在於對於前面計算過得信息不需要再重復計算，而brute
 force則每次重新計算。上面兩種算法中，動態規劃的時間復雜度是O(n^2),空間復雜度也是O(n^2)。而brute force的遞歸算法最壞情況是指數量級的復雜度。 

這種題目在面試中算是比較難的題目，因為分情況比較多，如果不熟悉比較難在面試中理清思路並且做對，我不是很喜歡，但是在面經中卻經常看到，所以還是得搞熟悉比較好。類似的題目有Wildcard
 Matching，那個還更簡單一些，不過思路是基本一致的，只是少分一點情況。