Write your code in the file StringRec.java. For this problem, the following rest
ID: 3581352 • Letter: W
Question
Write your code in the file StringRec.java. For this problem, the following restrictions apply:
YOUR CODE MUST BE RECURSIVE.
Do not use loops (while, do/while, or for).
Do not declare any variables outside of a method. You may declare local variables inside a method.
Complete the following method:
public static String decompress(String compressedText): Decompress the input text, which has been compressed using the RLE algorithm (previous hw assignment):
Run-length encoding (RLE) is a simple "compression algorithm" (an algorithm which takes a block of data and reduces its size, producing a block that contains the same information in less space). It works by replacing repetitive sequences of identical data items with short "tokens" that represent entire sequences. Applying RLE to a string involves finding sequences in the string where the same character repeats. Each such sequence should be replaced by a "token" consisting of:
the number of characters in the sequence
the repeating character
If a character does not repeat, it should be left alone.
For example, consider the following string:
After applying the RLE algorithm, this string is converted into:
In the compressed string, "9w" represents a sequence of 9 consecutive lowercase "w" characters. "5e" represents 5 consecutive lowercase "e" characters, etc.
You may assume that the character counts will be single-digit numbers (a character will not repeat more than 9 times consecutively).
Hint #1: remember that characters are represented by numeric codes. You can decrement a character variable as follows:
Hint #2: You probably will not need to use this hint for this problem. However, a fast way to convert a digit character into the numeric value of the digit is to subtract the character code for the digit zero:
Scoring:
50 points for Correct Solution
50 points recursive solution
Thank You.
Explanation / Answer
Please find my code.
Please let me know in case of any issue.
public class StringRec {
public static String decompress(String compressedText){
//System.out.println(compressedText);
// Base Case
if(compressedText == null || compressedText == "" || compressedText.length() == 1){
return compressedText;
}
char c = compressedText.charAt(0);
// if current current is digit
if(Character.isDigit(c)){
// if it is equal to 1
if(c == '1'){
// if it is the last character
if(compressedText.length() == 2)
return compressedText.substring(1);
else
return compressedText.charAt(1) + decompress(compressedText.substring(2));
}else{
return compressedText.charAt(1) + decompress((c - '0' -1) + compressedText.substring(1));
}
}else{
return c + decompress(compressedText.substring(1));
}
}
public static void main(String[] args) {
String compressed = "q9w5e2rt5y4qw2Er3T";
System.out.println("Decompresed of q9w5e2rt5y4qw2Er3T: "+decompress(compressed));
}
}
/*
Sample run:
Decompresed of q9w5e2rt5y4qw2Er3T: qwwwwwwwwweeeeerrtyyyyyqqqqwEErTTT
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.