面试题16.18.模式匹配

链接：面试题16.18.模式匹配
难度：Medium
标签：数学、字符串、回溯、枚举
简介：你有两个字符串，即 pattern 和 value。 pattern 字符串由字母"a"和"b"组成，用于描述字符串中的模式。例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断 value 字符串是否匹配 pattern 字符串。

题解 1 - typescript

• 编辑时间：2020-06-22
• 执行用时：84ms
• 内存消耗：37.3MB
• 编程语言：typescript
• 解法介绍：细节判断，复刻 java 代码，并没有很深的理解。

function patternMatching(pattern: string, value: string): boolean {
  // 如果为空字符串 则只能匹配空字符串
  if (pattern === '') return value === '';
  // 如果匹配字符串只有a或b
  if (pattern === 'a' || pattern === 'b') return true;
  // 计算pattern里a和b的个数
  let aCount = 0;
  let bCount = 0;
  for (const c of pattern) {
    if (c === 'a') aCount++;
    else bCount++;
  }
  const vLen = value.length;
  // value为空时，判断pattern是否只有a或只有b
  if (value === '') return aCount === 0 || bCount === 0;
  // a或b的数量为0，判断value能否被等分
  if (aCount * bCount == 0) {
    const count = aCount + bCount;
    if (vLen % count != 0) return false;
    let len = vLen / count;
    for (let i = len; i < vLen; i += len) if (!stringEquals(0, i, len)) return false;
    return true;
  }
  // i代表a字符串的长度
  for (let i = 0; i <= vLen; i++) {
    // a字符串过长就break
    if (vLen < aCount * i) break;
    const bLen = ~~((vLen - aCount * i) / bCount);
    // lenB满足条件才进行判断
    if (bLen * bCount + aCount * i !== vLen) continue;
    let index = 0;
    // 初始化a和b的初始索引之前设置为-1
    const ab = [-1, -1];
    let notMatch = false;
    for (const c of pattern) {
      if (c === 'a') {
        if (ab[0] === -1) ab[0] = index;
        else if (!stringEquals(ab[0], index, i)) {
          notMatch = true;
          break;
        }
        index += i;
      } else {
        if (ab[1] === -1) ab[1] = index;
        else if (!stringEquals(ab[1], index, bLen)) {
          notMatch = true;
          break;
        }
        index += bLen;
      }
      if (bLen === i && ab[0] !== -1 && ab[1] !== -1 && stringEquals(ab[0], ab[1], bLen)) {
        notMatch = true;
        break;
      }
    }
    // notMatch为false说明之前的几个判断里面都不是因为break跳出
    if (!notMatch) return true;
  }
  return false;
  function stringEquals(i: number, j: number, len: number): boolean {
    for (let k = 0; k < len; k++) if (value[i + k] !== value[j + k]) return false;
    return true;
  }
}