[LeetCode] 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:

Example 2:

Example 3:

字符串压缩。

题意是给一个字符串，请按规则压缩。压缩的结果还是存在char array中但是最后输出的是新的char array的长度。

基本逻辑是要求你把连续出现多个的字母转化成字母 + 出现次数的组合。要求是不使用额外空间。这个题我也不知道该归为什么算法或者方法，我这里解释一下我的思路吧。做一个while循环和一个指针，首先确保指针不能跳出while循环，条件自然是指针指向的index不能大于input字符串的长度。在遍历input的时候，如果遇到一个新的字母c，先记下这个字母，然后往后遍历看看这个字母是否有连续出现，若有，则需要记录连续出现的次数count。当连续出现的字符停止之后，此时可以试着将已经遍历过的部分写入res，因为你有了c和他的count，所以就可以写入res了。注意需要将count先转化成String.valueOf然后再转化成charArray，才能将比如12转化成"1", "2"这样的形式。只要count不等于1，那么这个数字就一定要被写入最后的char array。

时间O(n)

空间O(1) - 题目要求

Java实现

相关题目

38. Count and Say

271. Encode and Decode Strings

443. String Compression

604. Design Compressed String Iterator

1313. Decompress Run-Length Encoded List

LeetCode 题目总结