寫(xiě)一個(gè)簡(jiǎn)單的表達(dá)式匹配，這題我想了好久用非遞歸的方式來(lái)做，最后失敗了。問(wèn)題點(diǎn)是需要決策.和x出現(xiàn)的時(shí)候是否應(yīng)該匹配，有時(shí)候需要匹配有時(shí)候不匹配，無(wú)法用一次循環(huán)找條件做出來(lái)。

遞歸來(lái)做思想很簡(jiǎn)單 先看終止條件
1.s字符串長(zhǎng)度為0的時(shí)候 p字符串要么長(zhǎng)度為0 要么必須是以xxx*之類(lèi)的序列 否則無(wú)法匹配
2.p字符串長(zhǎng)度為0的時(shí)候 s字符串長(zhǎng)度也必須為0 否則無(wú)法匹配

來(lái)看遞歸規(guī)則
1.當(dāng)p字符串中p[1]不為的時(shí)候，比較s[0]與p[0]是否相等或p[0]是否為. 不相等不為.直接返回false 否則截取p[1]和s[1]后的字符串遞歸比較
2.當(dāng)p字符串中p[1]為的時(shí)候
1.若p[0] 為. 則截取i 進(jìn)行遞歸比較 (i為0-p字符串的長(zhǎng)度)
2.若p[0] 不為. 則判斷p[0]與s[i]的是否相等 相等截取i(i為0-p字符串長(zhǎng)度)

   /**
  * @param {string} s
  * @param {string} p
  * @return {boolean}
  */
  var isMatch = function(s, p) {
    var i = 0, j = 0, sl = s.length, pl = p.length;
    if(sl == 0) {
      if(pl == 0 || (p[1] == '*' && isMatch(s,p.slice(2))))
        return true;
      else
        return false;
    } else if (pl == 0) {
      return false;
    }

    if(p[1] !== '*') {
      if(s[0] === p[0] || p[0] === '.')
        return isMatch(s.slice(1), p.slice(1))
      else
        return false;
    } else {
      if(p[0] === '.') {
        while(i <= sl+1) {
          if(isMatch(s.slice(i),p.slice(2)))
            return true;
          i++;
        }
      } else {
        if(isMatch(s.slice(0),p.slice(2)))
          return true;
        while(i < sl && s[i] === p[0]) {
          if(isMatch(s.slice(i + 1),p.slice(2)))
            return true;
          i++;
        }
      }
      return false;
    }

  };