题目描述

利用字符重复出现的次数，实现基本的字符串压缩功能，如果压缩之后的字符串比原字符串长，则返回原字符串

例如 输入：aabccccc 输出：a2b1c5

问题分析

分两种情况：

1. 只压缩连续字符串，例如 aabcccccaaa => a2b1c5a3

   思路为基于栈，如果栈顶元素和下一个元素不一样，则push 进入count 和下一个元素同时重置一下count，否则count + 1

2. 需要同时压缩非连续重复出现的字符串，例如 aabcccccaaa => a5b1c5

   hash统计 + 两次遍历，先统计字符次数，和无重复字符串，再次遍历添加对应的数量；

代码实现

1. 只压缩连续字符串

function compressChar(str) {
  const res = [];
  let count = 0;
  let char = '';
  for (let i = 0; i < str.length; i++) {
    // 和下一个字符不相同
    if (char !== str[i]) {
      // 首次不需要push count
      count && res.push(count);
      res.push(str[i]);
      // 重置标记符
      char = str[i];
      count = 0;
    }
    count++;
  }
  // 需要把最后一次的count也加上
  res.push(count);
  
  const compressed = res.join('');

  return compressed.length > str.length ? str : compressed;
}

2. 需要同时压缩非连续重复出现的字符串

function compressString(str) {
  const charCount = {};
  const res = [];
  // 遍历，统计字符次数，并获取非重复字符串
  for (let i = 0; i < str.length; i++) {
    const c = str[i];
    if (!charCount[c]) {
      res.push(c);
      charCount[c] = 1;
    } else {
      charCount[c]++;
    }
  }
  let result = '';
  // 添加次数
  for (let i = 0; i < res.length; i++) {
    result += res[i] + charCount[res[i]];
  }
  return result.length > str.length ? str : result;
}