String Compression: Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. 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).
分析
连续的字符出现次数多少次才能有压缩收益？应该是>=3次，如果=2次则没有收益，如果=1次则反而会有惩罚。
所以本题的例子里有个错误，应该是a2bc5a3。
思路是遍历这个字符串，比较当前和前一个是否相等，如果相等则计数+1，如果不等则看计数是否>=2，根据情况变成【字母数字】这种形式还是保持原样，然后清零。
解法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
public String compress(String s) {
if (s.length <= 2) {
return s;
}
StringBuilder sb = new StringBuilder();
char prevChar = s.charAt(0);
int count = 1;
for(int i = 1; i <= s.length; i++) {
if (i == s.length) {
appendChar(sb, prevChar, count);
break;
}
char currChar = s.charAt(i);
if (currChar == prevChar) {
count++;
} else {
appendChar(sb, prevChar, count);
prevChar = currChar;
count = 1;
}
}
if (sb.length() >= s.length) {
return s;
}
return sb.toString();
}
private void appendChar(StringBuilder sb, char c, int count) {
if (count >= 2) {
sb.append(c);
sb.append(count);
} else {
sb.append(c);
}
}
|
时间复杂度：O(n)，n=原始字符串长度
空间复杂度：O(min(n, c))，c=压缩后的字符串长度
解法二
StringBuilder内部也是一个array，会有扩容的问题（和ArrayList一样）。如果可以事先计算出压缩字符串长度就能够固定StringBuilder的容量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
public String compress(String s) {
if (s.length <= 2) {
return s;
}
int compressedLength = compressedLength(s);
if (compressedLength >= s.length) {
return s;
}
StringBuilder sb = new StringBuilder(compressedLength);
char prevChar = s.charAt(0);
int count = 1;
for(int i = 1; i <= s.length; i++) {
if (i == s.length) {
appendChar(sb, prevChar, count);
break;
}
char currChar = s.charAt(i);
if (currChar == prevChar) {
count++;
} else {
appendChar(sb, prevChar, count);
prevChar = currChar;
count = 1;
}
}
return sb.toString();
}
private void appendChar(StringBuilder sb, char c, int count) {
if (count >= 2) {
sb.append(c);
sb.append(count);
} else {
sb.append(c);
}
}
private int compressedLength(String s) {
int compressedLength = 0;
char prevChar = s.charAt(0);
int count = 1;
for(int i = 1; i <= s.length; i++) {
if (i == s.length) {
compressedLength += compressedLength(count);
break;
}
char currChar = s.charAt(i);
if (currChar == prevChar) {
count++;
} else {
compressedLength += compressedLength(count);
prevChar = currChar;
count = 1;
}
}
return compressedLength;
}
private int compressedLength(int count) {
if (count <= 2) {
return count;
}
return 1 + String.valueOf(count).length;
}
|
评论