443. String Compression

443. String Compression

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

Follow up: Could you solve it using only O(1) extra space?

Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Example 3:

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

Note:

1. All characters have an ASCII value in [35, 126].

2. 1 <= len(chars) <= 1000.

My Solutions:

方法1：用 StringBuilder逐步建造新string

public int compress(char[] chars) {

    int count = 1; // 因为要比较当前字符和下一个字符，所以初始化count为1
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < chars.length; i++) {
        // 如果走到最后一个字符或者现在的字符和下一个字符不一样
        // 把字符加到sb里
        // 如果count不为1，把count加到sb里
        // 更新count
        if (i == chars.length - 1 || chars[i] != chars[i + 1]) {
            sb.append(chars[i]);
            if (count != 1) sb.append(count);
            count = 1;
        } else {
            count++;
        }
    }
    return sb.length();       
}        

方法2：in-place。用两个指针标记字母和重复字母的位置。

class Solution {
    public int compress(char[] chars) {
        if (chars == null || chars.length == 0) return 0;
        
        int res = 0, i = 0, j = 0;
        while (i < chars.length) {
            // if reach the end of the string or find a duplicate need to do compression
            if (j == chars.length || chars[i] != chars[j]){   
                chars[res++] = chars[i];
                if (j - i <= 1) {
                    i = j;
                } else {
                    // in case the num is >= 10
                    String num = Integer.toString(j - i); 
                    for (int k = 0; k < num.length(); k++) {
                        chars[res++] = num.charAt(k);
                    }
                    i = j;
                }
            } else {
                j++;
            }
        }
        return res;
    }
}