**
Question:

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

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", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

**

這是我寫過的最惡心的代碼！??！我連續(xù)寫了四個(gè)小時(shí)，針對(duì)不同的細(xì)節(jié)。及其繁瑣。
最后實(shí)在扛不住了，放棄了。
現(xiàn)在很累。實(shí)在看不動(dòng)分析了。明天再說吧

Referenced Code:

public class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }

        if (p.length() == 1 || p.charAt(1) != '*') {
            if (s.isEmpty() || (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0))) {
                return false;
            } else {
                return isMatch(s.substring(1), p.substring(1));
            }
        }

        //P.length() >=2
        while (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'))  {  
            if (isMatch(s, p.substring(2))) { 
                return true;                     
            }                                    
            s = s.substring(1);
        }

        return isMatch(s, p.substring(2));
    }
}

Test result:

Paste_Image.png

思路：
這次作業(yè)挺難的，很難的，對(duì)于我來說。。。
是一種模式識(shí)別，要考慮較多的情況。每次碰到這樣的編程題，程序員之間，或者說，碼農(nóng)和程序員之間的區(qū)別就會(huì)體現(xiàn)出來了。這是一種思路的區(qū)別。碼農(nóng)想到的一定是用if將各種情況考慮到，比如我。而真正的程序員，想到的一定是，以一種更加宏觀的思路，來解決這個(gè)問題，而不拘泥于細(xì)節(jié)。這種宏觀的思路，就是，遞歸。
Recursion has helped code become simple.
首先說下我犯下的錯(cuò)誤吧。
最嚴(yán)重的錯(cuò)誤，給出的兩個(gè)字符串，s , p, 其實(shí)只會(huì)在p中出現(xiàn) "." and "". 因?yàn)槭潜磉_(dá)式匹配，所以s中不會(huì)出現(xiàn)這些符號(hào)。
然后就是對(duì) ''含義的理解。"*"表示的是，前面那個(gè)字符出現(xiàn)的次數(shù)。
比如，

aa = a*
aaa = a*
ac = ab*c
....

這里會(huì)有幾個(gè)問題。
1.前面如果沒有字符，即他是字符串的首位，那么，他會(huì)想普通字符一樣與s中字符進(jìn)行比較。
2.若連續(xù)的出現(xiàn)，******,我們?nèi)詫⑺鼉蓚€(gè)兩個(gè)的分組，前面一個(gè)默認(rèn)為有意義的字符，后面一個(gè)才表示其出現(xiàn)的次數(shù)。所以前面一個(gè)*與普通字符作比較時(shí)永遠(yuǎn)是不相等的。所以一定是false。

3. ".*" 的情況比較特殊。

ab = .*
abc = .*
abcdefghijkldsadf = .*
abcd != .*c
abcd = .*abcd
abcd = .*bcd
abcd = .*cd
abcd = .*d
abcd = .*

可以看出，如果 .* 后面沒有尾巴，他與任何的s相匹配。如果有尾巴，他的尾巴必須與s中的尾巴相匹配。
4.該用何種思路來處理 * 的比較。
我一開始的思路，或者大多數(shù)人的思路，一定是貪婪算法。就是將*表示的次數(shù)刷到最大。比如：

aaa = a*
aaaaaab = a*b

這個(gè)時(shí)候我們會(huì)將*刷到最大。然后進(jìn)行下一組比較。但是，有些情況是特殊的，也是我最后發(fā)現(xiàn)的，然后決定放棄自己的思路看答案。

aaaaa = a*a

在這樣一個(gè)匹配中，如果用最大化 * 思路的話，那么就是不匹配的了， *會(huì)一直刷到s結(jié)束。然后p最后還有一個(gè) a。那就不匹配了。所以這個(gè)時(shí)候就得判斷, * 到底代表多少次。這并不是越大越好。我當(dāng)時(shí)也想了一些方法來處理這種情況。比如統(tǒng)計(jì)相同字符的個(gè)數(shù)。。。。后來覺得太復(fù)雜了。網(wǎng)上一看，果不其然，
用遞歸！

下來說下思路吧。
應(yīng)該分成兩種情況。
1.p中第二個(gè)字符不是""。 那么，該怎么比就怎么比。
2.p中第二個(gè)字符是""。那么。就需要用遞歸。
如果 s.charAt(0) == p.charAt(0) || p.charAt(0) == '.' ----> .* (萬能匹配)
那么，就會(huì)判斷， s是否與p.substring(2)，即p字符串剩下的部分匹配。如果匹配，那么就返回true。如果不匹配。
s = s.substring(1).
再判斷 s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'
如果滿足，繼續(xù)判斷 此時(shí)的s是否與p.substring(2)，即p字符串剩下的部分匹配。如果匹配，那么就返回true。如果不匹配。

aaa = a*a

比較次序是

s = aaa;
s != a;
s = aa;
s != a;
s = a;
s = a;
return true;

這就是這個(gè)代碼的基本思路。用遞歸來實(shí)現(xiàn)這種判斷，判斷s剩下的部分（尾部）是否與p的尾部相匹配。已經(jīng)，何處開始是s的尾部。

**
總結(jié)：
遞歸，感覺有種人工智能的感覺。其實(shí)也只是一種遍歷，但是這種遍歷，又包含了人的思維。因?yàn)樗拿看螆?zhí)行，不僅僅是簡(jiǎn)單的遍歷，還會(huì)將我們的思維再次重復(fù)執(zhí)行一遍。這就是遞歸。我的實(shí)力還遠(yuǎn)遠(yuǎn)達(dá)不到這個(gè)水平。。
而且這次寫代碼，我再次可以感受到，自己思維中的那些瑣碎的，冗余的想法。
而且以后有什么思路，一定要寫在紙上，尤其對(duì)于這么復(fù)雜的題目。情況一多，很多東西腦子里想到過，但后來又忘了。
**

Anyway, Good luck, Zhidong Liu!

My code:

public class Solution {
    public boolean isMatch(String s, String p) {
        if (p.length() == 0) {
            return s.length() == 0;
        }
        else if (p.length() == 1) {
            if (s.length() == 1 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) {
                return true;
            }
            else {
                return false;
            }
        }
        else if (p.charAt(1) != '*') {
            if (s.length() == 0) {
                return false;
            }
            else if (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') {
                return isMatch(s.substring(1), p.substring(1));
            }
            else {
                return false;
            }
        }
        else {
            if (isMatch(s, p.substring(2))) {
                return true;
            }
            while (s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) {
                 s = s.substring(1);
                if (isMatch(s, p.substring(2))) {
                    return true;
                }
            }
            return false;
        }
    }
}

看的同學(xué)的代碼，覺得邏輯很清楚。
dfs
首先，p每次移動(dòng)的單位是2位。所有，如果p中含有 *,那么，一定在index = 1 的位置。
所以，
首先判斷， p.length() == 0
如果等于 0， 那么s也必須等于0，否則就是false

然后，如果 p.length() == 1
那么，p不可能含有 *
所以可以簡(jiǎn)單地比較，
s.charAt(0) == p.charAt(0) || p.charAt(0)
此時(shí)可以返回true，否則返回false

如果p.length() >= 2 && p.charAt(1) != '*'
此時(shí)也可以放心的比較。
首先判斷s 長(zhǎng)度。如果已經(jīng)是0了，因?yàn)?p第二位不是 , 所以一定不match，返回false
如果s.length() > 0, 并且s.charAt(0) == p.charAt(0) || p.charAt(0)
那么，就可以比較， isMatch(s.substring(1), p.substring(1))
有人會(huì)問，這里不是只移動(dòng)了一格而沒有移動(dòng)兩格嗎？
因?yàn)榈诙徊皇?''啊。所以我們移動(dòng)一格并不會(huì)破壞順序。

如果p.length() >= 2 && p.charAt(1) == '*'

這個(gè)時(shí)候，* 可以代表0個(gè)或多個(gè)他前面的字符。
所以，首先，如果*代表0個(gè)，那么我直接匹配s and p.substring(2)
即，
if (isMatch(s, p.substring(2))) {...}

然后如果匹配不成功，這個(gè)時(shí)候我就需要移動(dòng) s 了
首先看 s.charAt(0) 是否與 p.charAt(0) 匹配。
如果匹配，ok,移動(dòng)一位，
s = substring(1);
然后匹配此時(shí)的 s and p
if (isMatch(s, p.substring(2))) {...}

如果不匹配。再判斷此刻的s(注意，這里的s已經(jīng)向右移動(dòng)了一位。)
if s.charAt(0) 和 p.charAt(0), 是否匹配。

如果不匹配，退出循環(huán)，直接返回 false 就行。

注意這里，只有 p 第二位是 '*',我每次都移動(dòng)兩位。

差不多就這樣了。這個(gè)解法比較通俗易懂，很不錯(cuò)。

一直記錄生活，計(jì)劃，的小筆記本丟了。很可惜。里面的東西也很復(fù)原了。幸虧上周把所有的日程記錄到了 Mac Calendar上，減少了些損失。是啊，如果我的小筆記本是放在云端的，怎么會(huì)丟呢？
但是電子設(shè)備記錄筆記，還是沒有紙質(zhì)筆記本的感覺好。
不知如何選。
這周經(jīng)歷了許多機(jī)會(huì)，許多失去。到現(xiàn)在，總體來說，還是收獲更多。下周，下下周，真正的挑戰(zhàn)就要來臨了?，F(xiàn)在還只是玩玩。
加油吧，多刷題，把簡(jiǎn)單medium 刷熟練了，高頻hard也刷熟練了。

Anyway, Good luck, Richardo! -- 09/16/2016