一天一大 leet(模式匹配)难度:中等 DAY-22

20200622

题目(难度:中等):

你有两个字符串，即 pattern 和 value。 pattern 字符串由字母"a"和"b"组成，用于描述字符串中的模式。
例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，“go"是"b”），该字符串也匹配像"a"、"ab"和"b"这样的模式。
但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断 value 字符串是否匹配 pattern 字符串

示例

• 示例 1

输入： pattern = "abba", value = "dogcatcatdog"
输出： true

• 示例 2

输入： pattern = "abba", value = "dogcatcatfish"
输出： false

• 示例 3

输入： pattern = "aaaa", value = "dogcatcatdog"
输出： false

• 示例 4

输入： pattern = "abba", value = "dogdogdogdog"
输出： true
解释： "a"="dogdog",b=""，反之也符合规则

提示

• 0 <= len(pattern) <= 1000
• 0 <= len(value) <= 1000
• 你可以假设 pattern 只包含字母"a"和"b"，value 仅包含小写字母。

抛砖引玉

特殊情况

1. 字符串为空且规则也为空 true
2. 字符串为空且规则包含一种字母(代表空)则 true，否则 false
3. 规则为空 字符串不为空 false

匹配
选规则中至少出现一次的字符进行逐位匹配；
匹配 a，
其包含匹配的字符数递增（记录 a 匹配的字符 value_a 和 b 匹配的字符 value_b）
如果 ab 匹配后字符数满足与 value 相同则返回 true，不然默认返回 false

/**
 * @param {string} pattern
 * @param {string} value
 * @return {boolean}
 */
var patternMatching = function (pattern, value) {
  let pLen = pattern.length,
    vLen = value.length,
    count_a = 0, // 字符串中a的数量
    count_b = 0 // 字符串中b的数量
  // 如果字符串为空
  // 1. 规则也为空 true
  // 2. 规则不为空，只包含一种字母(代表空)则true，否则false
  if (vLen === 0) {
    if (pLen == 0) return true
    if (pattern.includes('a') && pattern.includes('b')) {
      return false
    } else {
      return true
    }
  }
  // 规则为空 字符串不为空  false
  if (pLen == 0 && vLen !== 0) return false

  // 优化循环使用规则中较多的字符匹配，保证主动匹配的字符至少出现一次，统计字符数量
  for (let i = 0; i < pLen; i++) {
    if (pattern[i] === 'a') {
      count_a++
    } else {
      count_b++
    }
  }

  // 使用指定字符a进行主动匹配，如果a少于b那主动把a、b字符对调，
  if (count_a < count_b) {
    const t = count_a
    count_a = count_b
    count_b = t
    let s = ''
    for (let i = 0; i < vLen; i++) {
      if (pattern[i] === 'a') {
        s += 'b'
      } else {
        s += 'a'
      }
    }
    pattern = s
  }

  // a表示匹配字符a在字符串中代表的字符数，
  // n是剩余需要d匹配的字符
  // pos记录a字母在字符串中匹配的位置
  // value_a a匹配的字符串组
  // value_b b匹配的字符串组
  for (let a = 0; count_a * a <= vLen; a++) {
    const n = vLen - count_a * a
    if ((count_b === 0 && n === 0) || (count_b !== 0 && n % count_b === 0)) {
      const b_len = count_b === 0 ? 0 : Math.floor(n / count_b)
      let pos = 0
      let sign = true
      let value_a = ''
      let value_b = ''
      for (let i = 0; i < pLen; i++) {
        if (pattern[i] === 'a') {
          const sub = value.substr(pos, a)
          if (!value_a.length) {
            value_a = sub
          } else if (value_a !== sub) {
            sign = false
            break
          }
          pos += a
        } else {
          const sub = value.substr(pos, b_len)
          if (!value_b.length) {
            value_b = sub
          } else if (value_b !== sub) {
            sign = false
            break
          }
          pos += b_len
        }
      }
      if (sign && value_a !== value_b) {
        return true
      }
    }
  }
  return false
}

其他解法

\1 和 \2 表示对前面分组的反向引用

• aabb -> (\w*)\1(\w*)\2
• abba -> (\w*)(\w*)\2\1

//**
 * @param {string} pattern
 * @param {string} value
 * @return {boolean}
 */
var patternMatching = function (pattern, value) {
      if (pattern === "") {
    return value === "";
  }
  let group = 1;
  let a = '';
  let b = '';
  let reg = '';
  for (const char of pattern.split('')) {
    if (char === 'a') {
      if (a) {
        reg += a;
      }
      else {
        reg += '(\\w*)';
        a = '\\' + group++;
      }
    }
    else if (char === 'b') {
      if (b) {
        reg += b;
      }
      else {
        reg += '(\\w*)';
        b = '\\' + group++;
      }
    }
  }
  const match = new RegExp('^' + reg + '$').exec(value);
  return Boolean(match) && match[1] !== match[2];
}

博客: 小书童博客(http://gaowenju.com)

公号: 坑人的小书童