Created
February 7, 2014 20:01
-
-
Save Jeffwan/8870621 to your computer and use it in GitHub Desktop.
Basic String Compression Input: aabbc Output: a2b2c1 CC 150 - Arrays and Strings
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package leetcode; | |
import java.util.HashMap; | |
import java.util.Iterator; | |
import java.util.LinkedHashMap; | |
import java.util.Map; | |
import java.util.Map.Entry; | |
import java.util.Set; | |
/** | |
* aabcccccaaa --> a2b1c5a3 | |
* PS: like aa repeat is continious... Actually don't need to Use HashMap to statistic -- like book first | |
* | |
* | |
* Still two ways to solve this problem. more efficient | |
*/ | |
public class Compression { | |
public static void main(String args[]) { | |
String str = "aabcccccaaa"; | |
System.out.println(compression(str)); | |
} | |
/** | |
* Book frist Solution O(n+k2) | |
* Same as Two pointer, if char changed, stop and append the char the repeat number | |
*/ | |
public static String compression(String str) { | |
StringBuffer sb = new StringBuffer(); | |
char last = str.charAt(0); | |
int count = 0; | |
for (int i=0; i< str.length(); i++) { | |
if (str.charAt(i) == last) { | |
count++; | |
} else { | |
sb.append(last + "" + count); | |
count = 1; // here count should be 1 but not 0 | |
} | |
last = str.charAt(i); | |
} | |
sb.append(last + "" + count); //reflush the last part | |
String newStr = sb.toString(); | |
if (newStr.length() < str.length()) { | |
return newStr; | |
} else { | |
return str; | |
} | |
} | |
/** | |
* My Solution: Store every number frequency and then Reconstruct them use a StringBuffer | |
* not efficient because of two loop | |
*/ | |
public static String compression2(String str) { | |
Map<Character, Integer> map = new LinkedHashMap<Character, Integer>(); | |
for (int i=0; i<str.length(); i++) { | |
char value = str.charAt(i); | |
if(map.containsKey(value)) { | |
int count = map.get(value) + 1; | |
map.put(value, count ); | |
} else { | |
map.put(value, 1); | |
} | |
} | |
// construct string | |
StringBuffer sb = new StringBuffer(); | |
Set<Entry<Character, Integer>> entrySet = map.entrySet(); | |
Iterator<Entry<Character, Integer>> iterator = entrySet.iterator(); | |
while (iterator.hasNext()) { | |
Entry<Character, Integer> entry = iterator.next(); | |
sb.append(entry.getKey()); | |
sb.append(entry.getValue()); | |
} | |
String newStr = sb.toString(); | |
// exclude situation like abc --> a1b1c1 | |
if (newStr.length() < str.length()) { | |
return newStr; | |
} else { | |
return str; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
String str= "aabbcccaaaa";
o/p: a2b2c3a4