Input and output For example, the text How, itu tells Onut hel future UU ofutheu
ID: 3844484 • Letter: I
Question
Input and output For example, the text How, itu tells Onut hel future UU ofutheuraptureuthatuimpels toutheuswinginguandutheuringinguofutheubells, ubells,ubells, ofutheubells Ubells U U U toutheurhyminguandutheuchiminguofutheubells. Edgar AllanuPoe becomes OUOnLutheufuture UU iti tells How, ofu6uraptureuthatuimpels tou 5Lu swinging andu3LuringingU9U3 bells,U1,U1, 3, 13, 13, I1 JU JU U UTUOU UUUU Edgar Allan Poe OUUncompressed U233Ubytes UU Compressed U17 Ubytes after compression. Conversely, decompressing the second text should produce the original text above.Explanation / Answer
/**
*
* @author Sam
*/
public class TextCompression {
class Node {
String word;
int count;
Node next;
Node prev;
Node(String word){
this.word = word;
next = prev = null;
count = 0;
}
}
Node head;
private void parseString(String str) {
String[] tokens = str.split(" ");
Node tmp = null;
for (String s:tokens)
if (head == null)
tmp = head = new Node(s);
else {
tmp.next = new Node(s);
tmp.next.prev = tmp;
tmp = tmp.next;
}
}
private void replace() {
Node tmpForward = head;
Node tmpBack;
int count;
while(tmpForward != null) {
tmpBack = tmpForward.prev;
count = 1;
while (tmpBack!=null) {
if (tmpBack.word.equals(tmpForward.word)) {
tmpForward.count = count;
break;
}
tmpBack = tmpBack.prev;
count ++;
}
tmpForward = tmpForward.next;
}
}
public String compress(String str) {
head = null;
parseString(str);
replace();
Node word = head;
String out = "0";
String tmp = "";
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ' ') {
if (!tmp.equals("")) {
out = out + " " + (word.count==0?word.word:word.count);
word = word.next;
}
else
out = out + " ";
tmp = "";
}
else
tmp = tmp + str.charAt(i);
}
out = out + " " + (word.count==0?word.word:word.count);
return out;
}
public static void main(String[] args) throws IOException {
TextCompression tc = new TextCompression();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println(tc.compress(br.readLine()));
}
}
This is how you compress... :) I hope this helped you :)