2022-09-28笔试题00
请注意,本文编写于 564 天前,最后修改于 564 天前,其中某些信息可能已经过时。

题目

Given a compressed string, return its original form.

For example.

uncompress('3(ab)') // 'ababab'
uncompress('3(ab2(c))') // 'abccabccabcc'

a number k followed by a pair of parenthesis, meaning to repeat the substring inside the parenthesis by k times, k is positive integer. inputs are guaranteed to be valid input like above example, there is no numerical digit in original form.

解析:

Intuition

Look at example 3(ab2(c)). At first, we see 3( which means we need to repeat 3 times anything that lies ahead. But how do we know the final status of what's next and how do we store the number of times we need to repeat it? It leads us to the fact we need to process the deepest string first, gradually returning to the beginning. This basically means we have 2 ways of doing it:

  1. Recursion — on each ( we recursively call the function until we reach the bottom and then bubble, constructing the final string until we return to the beginning.
  2. Stack — the same as recursion, but in an iterative manner. I like it more because we don't have to process parentheses.

About regexp

I use it only for simplicity to tokenize the number. The solution doesn't rely on regexp so we can easily replace it with a dictionary or something like this.

function uncompress(str) {
  let stack = [];
  let count = [];

  stack.push('');

  let i = 0;

  while (i < str.length) {
    let char = str[i];

    if (/\d/.test(char)) {
      let start = i;
      while (/\d/.test(str[i + 1])) i++;
      count.push(Number(str.substring(start, i + 1)));
    } else if (char === '(') {
      stack.push('');
    } else if (char === ')') {
      let times = count.pop();
      let str = stack.pop();
      let tmp = '';

      for (let j = 0; j < times; j++) tmp += str;

      stack.push(stack.pop() + tmp);
    } else {
      stack.push(stack.pop() + char);
    }

    i++;
  }

  return stack.pop();
}

本文作者:前端小毛

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!