#10 Regular Expression Matching

写一个简单的表达式匹配，这题我想了好久用非递归的方式来做，最后失败了。问题点是需要决策.和x出现的时候是否应该匹配，有时候需要匹配有时候不匹配，无法用一次循环找条件做出来。

递归来做思想很简单 先看终止条件
1.s字符串长度为0的时候 p字符串要么长度为0 要么必须是以xxx*之类的序列 否则无法匹配
2.p字符串长度为0的时候 s字符串长度也必须为0 否则无法匹配

来看递归规则
1.当p字符串中p[1]不为的时候，比较s[0]与p[0]是否相等或p[0]是否为. 不相等不为.直接返回false 否则截取p[1]和s[1]后的字符串递归比较
2.当p字符串中p[1]为的时候
1.若p[0] 为. 则截取i 进行递归比较 (i为0-p字符串的长度)
2.若p[0] 不为. 则判断p[0]与s[i]的是否相等 相等截取i(i为0-p字符串长度)

   /**
  * @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;
    }

  };