面试题 01.06. 字符串压缩、栈

面试题 01.06. 字符串压缩

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a 至 z）。
示例 1:

输入："aabcccccaaa"
 输出："a2b1c5a3"

示例 2:

输入："abbccd"
输出："abbccd"
解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。

提示：

1. 字符串长度在[0, 50000]范围内。

思路

栈

使用栈记录出现的元素和个数，最后再转化为字符串

优化空间

很显然不需要栈进行维护，只需要判断是否是新的字符即可，使用一个 temp 数组，第一项是字符，第二个是连续出现的个数。遍历字符串，如果是新的字符就将临时记录的 temp 拼接加到结果字符串中，不是新的字符就继续计数。

解答

栈

/**
 * @param {string} S
 * @return {string}
 */
var compressString = function (S) {
  if (!S) return "";
  const stack = [[S[0], 0]];
  for (const arr of S) {
    if (stack[stack.length - 1][0] === arr) stack[stack.length - 1][1]++;
    else stack.push([arr, 1]);
  }
  const res = stack.map(([a, b]) => a + b).join("");
  return res.length >= S.length ? S : res;
};

优化空间

/**
 * @param {string} S
 * @return {string}
 */
var compressString = function (S) {
  if (!S) return "";
  let temp = [S[0], 0];
  let res = "";
  for (const arr of S) {
    if (temp[0] === arr) temp[1]++;
    else {
      res += temp[0] + temp[1];
      temp = [arr, 1];
    }
  }
  res += temp[0] + temp[1];
  return res.length >= S.length ? S : res;
};