正则表达式匹配

07/03/2021

leetcode-正则表达式匹配

题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：

输入：s = "ab", p = "."
输出：true
解释："." 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

1 <= s.length <= 20
1 <= p.length <= 20
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

本人题解

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
  if (s === p) {
    return true;
  } else {
    var sArr = s.split(''), pArr = p.split('');
    if(getMatch(sArr, sArr.length-1, pArr)) {
      return true
    } else {
      return false
    }
  }
};
 
var getLastChar = function(arr) {
  for (var i = arr.length - 1; i >= 0; i--) {
    if(arr[i] != "*")
      return arr[i]
  }
}
 
var testEnd = function(pArr) {
  if (pArr.length == 0) {
    return true
  }
  if (pArr[pArr.length - 1] !== "*") {
    return false
  }
  var lastRealChar = getLastChar(pArr);
  pArr = pArr.slice(0, pArr.lastIndexOf(lastRealChar));
  return testEnd(pArr)
}
 
var getMatch = function(sArr, index, pArr) {
  if (index == -1) {
    if (testEnd(pArr)) {
      return true
    } else {
      return false;
    }
  } else if (pArr.length === 0) {
    return false;
  }
 
  var isMatch = false;
  
  var lastEle = pArr[pArr.length-1];
  if (lastEle === sArr[index] || lastEle === '.') {
    pArr.pop();
    isMatch = isMatch || getMatch(sArr, index-1, pArr);
  } else if (lastEle !== "*") {
    return false
  } else {
    var lastRealChar = getLastChar(pArr);
    if (lastRealChar === sArr[index] || lastRealChar === '.') {
      isMatch = isMatch || getMatch(sArr, index-1, pArr);
    } 
    // else {
      pArr2 = pArr.slice(0, pArr.lastIndexOf(lastRealChar));
      isMatch = isMatch || getMatch(sArr, index, pArr2);
    // }
  }
  return isMatch;
}

分析

忘了。以后再补