Question

Run-length encoding is a relatively simple technique for compressing data; if a particular value (or substring) appears multiple times in a row, it is only represented once, followed by an integer indicating the number of times it should be repeated. For example, the string "AAAAA" can be compressed to "A5" (5 occurrences of 'A'), saving three characters in the process.

Define a Java method named expand() that takes a single String argument. You may assume that this String is run-length encoded and contains an even number of characters (each pair of characters consists of a printing character followed by a single digit representing its repetition count). Your method should return a new String that contains the expanded (or decoded) version of its argument. For example, calling expand(“a3b7a2c4") would return the String “aaabbbbbbbaacccc”.

Complete this problem by writing a complete Java program that prompts the user to enter a run-length encoded string, passes it to your expand() method, and displays the decoded result.

Hint: Java’s Integer.parseInt() method may be helpful here if you want to avoid performing character arithmetic.

Answer 1

public class CompressExpandString {

/**

* method to encode the string

*

* @param s

* @return

*/

public static String encoding(String s) {

int count = 1;

int mark = 0;

StringBuilder builder = new StringBuilder();

for (int i = 1; i < s.length(); i++) {

if (s.charAt(i) == s.charAt(i - 1) && i < s.length() - 1) {

count++;

} else if (i == s.length() - 1 && s.charAt(i) == s.charAt(i - 1)) {

count++;

builder.append(s.charAt(mark));

builder.append(count);

count = 1;

mark = i;

} else {

builder.append(s.charAt(mark));

builder.append(count);

count = 1;

mark = i;

}

}

return builder.toString();

}

/**

* method to expand the string

*

* @param input

* @return

*/

public static String expand(String input) {

StringBuilder result = new StringBuilder();

Character currentCharacter;

int times;

for (int i = 0; i < input.length(); i++) {

currentCharacter = input.charAt(i);

if (Character.isDigit(currentCharacter)) {

times = Integer.parseInt(currentCharacter + "");

for (int j = 0; j < times; j++) {

result.append(input.charAt(i - 1));

}

}

}

return result.toString();

}

public static void main(String z[]) {

String input = "aaabbbbbbbaacccc";

String compressed = encoding(input);

String expand = expand(compressed);

System.out.println("Input : " + input);

System.out.println("Encodded : " + compressed);

System.out.println("Expanded : " + expand);

}

}

OUTPUT:

Input : aaabbbbbbbaacccc
Encodded : a3b7a2c4
Expanded : aaabbbbbbbaacccc