面试题 01.06 字符串压缩

Posted on | In
Words count in article: 283 | Reading time ≈ 1

题目

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

示例1：

1
2
输入："aabcccccaaa"
输出："a2b1c5a3"

示例2：

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

解法

解法一：

遍历时统计

初始化时，currentChar是字符串的第一个字符

从1开始，如果当前位置上的字符，等于currentChar，count++，否则，将当前字符追加到sb上，然后currentChar设为当前字符，count重置为1

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String compressString(String S) {
        if (S == null || S.length() <= 2) {
            return S;
        }
        
        char[] chars = S.toCharArray();
        
        StringBuilder sb = new StringBuilder();
        int currentChar = chars[0];
        int count = 1;
        for (int i = 1; i < S.length(); i++) {
        	if (chars[i] == currentChar) {
        		count++;
        	} else {
        		sb.append((char) currentChar).append(count);
        		currentChar = chars[i];
        		count = 1;
        	}
        }
        return sb.append((char) currentChar).append(count).length() < S.length() ? sb.toString(): S;
    }
0%