欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-07 23:02:32
...

20200622

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

题目(难度:中等):

你有两个字符串,即 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 仅包含小写字母。

抛砖引玉

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

特殊情况

  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)

公号: 坑人的小书童
一天一大 leet(模式匹配)难度:中等 DAY-22