213. String Compression【easy】
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 upper and lower case letters (a-z).
str=aabcccccaaa
return a2b1c5a3
str=aabbcc
return aabbcc
str=aaaa
return a4
解法一:
public class Solution {
/**
* @param str a string
* @return a compressed string
*/
public String compress(String str) {
// Corner case
if (str == null) {
return null;
} else if (str.length() <= 2) {
return str;
} StringBuilder sb = new StringBuilder();
char temp = str.charAt(0);
int count = 1; for (int i = 1; i < str.length(); i++) {
// If same char continues, then add the count
if (str.charAt(i) == temp) {
count++;
} else {
// Encounter different char, set temp to the char and count to 1
sb.append(temp);
sb.append(count);
temp = str.charAt(i);
count = 1;
}
} // Do not forget the last char and the count!!!
sb.append(temp).append(count); // Compare the result of original str with the new stringbuilder
if (sb.length() >= str.length()) {
return str;
} else {
return sb.toString();
}
}
}
Here we use StringBuilder to create a new String, instead of String concatenation. That’s because for String concatenation operation, it’ll build a new string for every operation.
The basic algorithm is:
1、Create stringbuilder and initialize the first temp char, with count = 1
2、Go through the string char by char
(1)If char(i) equals to temp, continue and add count
(2)If not, add the temp and count to stringbuilder, reset the temp to be char(i) and count to be 1
3、Go out of the loop and add the last char and count for it
4、Compare the stringbuilder with initial str
Note: After go through the for loop, the temp is equals the last - 1 char, so we need to add the last char with its count.
Time complexity: O(n)
Space complexity: O(n)
参考@Steven Wu 的代码
https://codebysteven.wordpress.com/2016/03/14/lintcode-string-compression/
解法二:
public class Solution {
/*
* @param str: a string
* @return: a compressed string
*/
public String compress(String str) {
if (str == null || str.length() < 3) {
return str;
}
StringBuilder sb = new StringBuilder();
Map<Character, Integer> map = new HashMap<>();
char pre = str.charAt(0);
map.put(pre, 1);
for (int i = 1; i < str.length(); i++) {
char cur = str.charAt(i);
if (cur == pre) {
map.put(pre, map.get(pre)+1);
} else {
sb.append(pre);
sb.append(map.get(pre));
map.put(pre, 0);
map.put(cur, 1);
pre = cur;
}
}
sb.append(pre);
sb.append(map.get(pre));
String res = sb.toString();
return res.length() < str.length() ? res : str;
}
}
参考@linspiration 的代码
https://segmentfault.com/a/1190000012634492
最新文章
- 1208PHP语句
- zookeeper能做什么?
- IOS Core Animation Advanced Techniques的学习笔记(四)
- TAR命令详解
- 有关PHP安装,基础学习
- 【LeetCode 231】Power of Two
- java线程中的wait和notify以及notifyall
- php 10.1总
- 在H3C交换机上开通一个VLAN并且开通一个端口ping通它
- Hexo:创建属于你自己的博客
- centos6.5环境通达OA数据库mysql5.0.67升级至mysql5.5.48方案
- 2018-2019-2 网络对抗技术 20165333 Exp4 恶意代码分析
- 【Java】 剑指offer(50-2) 字符流中第一个只出现一次的字符
- 强化学习4-时序差分TD
- Java反编译工具Jad详解
- Java并发包中CyclicBarrier的源码分析和使用
- layui水平导航条三级
- centos 6.5 文件目录管理
- C++11新特性之五——可变参数模板
- csr867x开发日记——常用软件工具介绍