极客时间返利平台,你可以在上边通过山月的链接购买课程,并添加我的微信 (shanyue94) 领取返现。

# 关于字符串编码解码进阶

更多描述

一道有意思的面试题 例子如下,实现countOfLetters

countOfLetters("A2B3"); // { A: 2, B: 3 }
countOfLetters("A(A3B)2"); // { A: 7, B: 2}
countOfLetters("C4(A(A3B)2)2"); // { A: 14, B: 4, C: 4 }

Issue

欢迎在 Gtihub Issue 中回答此问题: Issue 625 (opens new window)

Author

回答者: Nctdtman (opens new window)

答案:

type LetterCounter = {
  // A-Z
  [i: string]: number;
};

function letterAddCount(target: LetterCounter, source: LetterCounter) {
  for (let k in source) {
    target[k] ??= 0;
    target[k] += source[k];
  }
  return target;
}
function letterMultipleCount(target: LetterCounter, multiples: number) {
  for (let i in target) {
    target[i] *= multiples;
  }
  return target;
}
function countOfLetters(str: string) {
  const regex = /[1-9]/;
  const stack: LetterCounter[] = [{}];
  for (let i = 0; i < str.length; i++) {
    const ch = str[i];
    let count = 1;
    if (regex.test(str[i + 1])) count = +str[++i]; // case ( | )
    switch (ch) {
      case "(":
        stack.push({});
        continue;
      case ")":
        const pop = stack.pop()!;
        const last = stack[stack.length - 1];
        letterAddCount(last, letterMultipleCount(pop, count));
        continue;
    } // case A-Z
    const last = stack[stack.length - 1];
    last[ch] ??= 0;
    last[ch] += count;
  }
  return stack.pop();
}
function countOfLetters(str) {
  let stack = [];
  const len = str.length;
  const pick = () => stack[stack.length - 1];
  const isNumber = (v) => !Number.isNaN(parseInt(v));
  for (let i = 0; i < len; i++) {
    const s = str[i];
    if (pick() === ")" && isNumber(s)) {
      let subStr = "";
      while (pick() !== "(") {
        let letter = stack.pop();
        if (letter !== ")") {
          if (isNumber(letter)) {
            subStr = +letter * parseInt(s) + subStr;
          } else if (isNumber(subStr.charAt(0))) {
            // 字母后跟着数字则直接拼接
            subStr = letter + subStr;
          } else {
            subStr = letter + s + subStr; // 字母后没有跟数字,需要将外层数字累加
          }
        }
      }
      // 弹出'('
      stack.pop();
      // 重新入栈
      stack = stack.concat(subStr.split(""));
      continue;
    }
    stack.push(s);
  }

  let result = {};
  let count = "";
  while (stack.length) {
    const s = stack.pop();
    if (isNumber(s)) {
      count = s + count;
    } else {
      result[s] = (result[s] || 0) + parseInt(count || "1");
      count = "";
    }
  }
  return result;
}

Author

回答者: hwb2017 (opens new window)

不用栈,全部用正则实现

const countOfLetters = (str) => {
  let frequencyMap = {};
  let regArray = [
    /([a-zA-Z])([a-zA-Z])/g, //AA
    /([a-zA-Z])(\))/g, //A)
    /([a-zA-Z])(\()/g, //A(
    /(\))([a-zA-Z])/g, //)A
    /(\))(\))/g, //))
    /(\))(\()/g, //)(
  ];
  let targetStr = str;
  for (const reg of regArray) {
    targetStr = targetStr.replace(reg, "$11$2");
  }
  // let targetStr = str.replace(/([a-zA-Z]|\))(\(|[a-zA-Z]|\))/g,"$11$2") // 这种写法最后一个测试用例会通过不了
  let unfoldable = /(\([0-9a-zA-Z]*\))([0-9]+)/;
  while (unfoldable.test(targetStr)) {
    targetStr = targetStr.replace(unfoldable, (match, p1, p2) =>
      p1.slice(1, -1).replace(/[0-9]+/g, (count) => +count * p2)
    );
  }
  let matchResult;
  let unit = /[a-zA-Z][0-9]+/g;
  while ((matchResult = unit.exec(targetStr)) !== null) {
    let letter = matchResult[0][0];
    let frequency = matchResult[0].slice(1);
    frequencyMap[letter] = frequencyMap[letter]
      ? frequencyMap[letter] + Number(frequency)
      : +frequency;
  }
  return frequencyMap;
};

console.log(countOfLetters("A2B3"));
console.log(countOfLetters("A(A3B)2"));
console.log(countOfLetters("C4(A(A3B)2)2"));
console.log(countOfLetters("C4(A()2)2"));
console.log(countOfLetters("(A2B3)"));
console.log(countOfLetters("(A11B9)11"));
console.log(countOfLetters("(A2B3)(A5B6)"));
console.log(countOfLetters("(A2B3)C(A5B6)"));
Last Updated: 11/27/2021, 6:11:48 PM