字符串压缩

发表于 | 分类于 |
字数统计: 468 字 | 阅读时长 ≈ 1 分钟

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

示例1:
输入：”aabcccccaaa”
输出：”a2b1c5a3”

示例2:
输入：”abbccd”
输出：”abbccd”
解释：”abbccd”压缩后为”a1b2c2d1”，比原字符串长度更长。

提示：
字符串长度在[0, 50000]范围内。

双指针

ccw-01-06.001.png

  • 令 i 指向字符串的「首个字符」， j 向前遍历，直到访问到「不同字符」时停止，此时 j - i 便是「首个字符」的连续出现次数，即可完成首个字符的压缩操作。
  • 接下来，从下个字符开始，重复以上操作，直到遍历完成即可。
  • 根据题目要求，最终返回「原字符串」和「压缩字符串」中长度较短的那个。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var compressString = function(S) {
  let i = 0, j = 0, len = S.length
  let res = []
  // 「外层循环」i 指向每个首次出现的字符
  while(i < len) {
    // 「内层循环」j 向前遍历，直到字符串末尾或找到与 s[i] 不同的字符时跳出
    while(j < len && S[i] === S[j]) {
      j++
    }
    // 压缩字符串，添加至 res
    res.push(S[i])
    res.push(j - i)
    // 令 i 指向下一个首次出现的字符
    i = j
  }
  // 对比「压缩字符串」和「原字符串」长度，返回较短的
  return res.length < len ? res.join('') : S
};

复杂度分析

  • 时间复杂度：O(N)。其中 N 为输入字符串 S 长度。指针 i , j 皆完成一次字符串遍历，循环 N + N = 2N+N=2N 次

  • 空间复杂度：O(1)。只需要常数空间（不包括存储答案的空间）存储变量。