541，字符串压缩，视频演示

Original 博哥数据结构和算法 2022-05-19

收录于合集 #算法图文分析 161个

Live life to the fullest.

尽情地享受生活吧。

问题描述

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

示例1:

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

示例2:

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

提示：

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

问题分析

这题是让统计连续相同字符的数量，非常简单的一道题，我们来看下解题思路

使用一个变量curChar记录当前字符，一个变量curCharCount记录当前字符出现的次数
当遇到新字符的时候，就把curChar和curCharCount加入到结果res中，然后再对curChar和curCharCount重新初始化。

重复上面的重复，直到把所有的字符遍历完为止

我们就以示例1为例来看下视频演示

再来看下代码

 1public String compressString(String S) {
 2    //边界条件判断
 3    if (S == null || S.length() == 0)
 4        return S;
 5
 6    StringBuilder res = new StringBuilder();
 7    //当前字符
 8    char curChar = S.charAt(0);
 9    //当前字符的数量
10    int curCharCount = 1;
11    for (int i = 1; i < S.length(); i++) {
12        //如果当前字符有重复的，统计当前字符的数量
13        if (S.charAt(i) == curChar) {
14            curCharCount++;
15            continue;
16        }
17        //走到这里，说明遇到了新的字符，
18        //这里先把当前字符和他的数量加入到res中
19        res.append(curChar).append(curCharCount);
20        //然后让当前字符指向新的字符，并且数量也要
21        //重新赋值为1
22        curChar = S.charAt(i);
23        curCharCount = 1;
24    }
25    //因为上面计算的时候会遗漏最后一个字符和他的数量,
26    //这要添加到res中
27    res.append(curChar).append(curCharCount);
28
29    //根据题的要求，若“压缩”后的字符串没有变短，
30    // 则返回原先的字符串
31    return res.length() >= S.length() ? S : res.toString();
32}

还可以换另一种方式，先把当前字符加入到res中，当遇到新的字符的时候再把当前字符的数量加进来，其实原理都差不多，我们来看下

 1public String compressString(String S) {
 2    //边界条件判断
 3    if (S == null || S.length() == 0)
 4        return S;
 5    StringBuilder res = new StringBuilder();
 6    //先把第一个字符添加到res中
 7    res.append(S.charAt(0));
 8    int count = 1;
 9    for (int i = 1; i < S.length(); i++) {
10        //判断重复字符的数量
11        if (S.charAt(i) == S.charAt(i - 1)) {
12            count++;
13            continue;
14        }
15        //走到这里，说明遇到了新的字符，先把前面字符
16        //的数量添加到res中，然后再添加这个新的字符
17        res.append(count).append(S.charAt(i));
18        count = 1;
19    }
20    //上面的计算会遗漏最后一个字符的数量，这里加上
21    res.append(count);
22    return res.length() >= S.length() ? S : res.toString();
23}