【Q607】关于字符串编码解码进阶

[Nctdt]

一道有意思的面试题 例子如下，实现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 }

[Nctdt]

答案：

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()
}

[haotie1990]

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;
}

[hwb2017]

不用栈，全部用正则实现

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)'))

[JamiLanister]

function replaceSubstring(str, start, end, replacement) {
    const startstr = str.substring(0, start)
    const endstr = str.substring(end+1)
    return startstr + replacement + endstr
}

function countOfLetters(s) {
    const flatObj = {}
    function handle(slices) {
        let left = 0;
        let right = slices.length-1
        let str = slices
        while (left < right ) {
            if (slices[left] === '(') {
                while (left < right) {
                    if (slices[right] === ')') {
                        const res = handle(slices.slice(left+1, right))
                        let num = Number(slices[right+1])
                        if (!isNaN(num)) {
                            str = replaceSubstring(slices, left, right+1, res.repeat(num))
                        }
                        return str
                    } else {
                        right--
                    }
                }
            } else {
                left++;
            }
        }

        return str
    }
    const flated = handle(s)
    for (let index=0; index<flated.length; index++) {
        const char = flated[index]
        const nextChar = flated[index+1]
        if (char.match(/\d/)) {
            continue
        }
        console.log(char, nextChar)
        if (!isNaN(Number(nextChar))) {
            flatObj[char] = flatObj[char] ? flatObj[char] + Number(nextChar) : Number(nextChar)
        } else {
            flatObj[char] = flatObj[char] ? flatObj[char] + 1 : 1
        }
    }
    return flatObj
}

console.log(countOfLetters("C4(A(A3B)2)2")) // { A: 14, B: 4, C: 4 }