【LeetCode程序员面试金典】面试题 01.06. Compress String LCCI

Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).

Example 1:

Input: "aabcccccaaa" Output: "a2b1c5a3" Example 2:

Input: "abbccd" Output: "abbccd" Explanation: The compressed string is "a1b2c2d1", which is longer than the original string.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/compress-string-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JAVA 字符串 直接 用串感觉内存一定爆炸

所以要用字符数组 StringBuilder

双指针判断

class Solution {
    public String compressString(String S) {
    int N = S.length();
    int i = 0;
    StringBuilder sb = new StringBuilder();
    while (i < N) {
        int j = i;
        while (j < N && S.charAt(j) == S.charAt(i)) {
            j++;
        }
        sb.append(S.charAt(i));
        sb.append(j - i);
        i = j;
    }

    String res = sb.toString();
    if (res.length() < S.length()) {
        return res;
    } else {
        return S;
    }
}
}

在 C++ 中，res += s 和 res = res + s 的含义是不一样的。前者是直接在 res 后面添加字符串；后者是用一个临时对象计算 res + s，会消耗很多时间和内存