Length-Prefixed Encoding
Problem
Every input line has words separated by single spaces. Encode the words like a tiny serialization format: each word becomes length:word, and the pieces are joined with commas (the words can themselves contain commas and colons, so you cannot split on them). Then decode the encoded text again, reading only the length prefixes, and print: encoded -> decoded, where the decoded words are joined with |. For example abc x becomes 3:abc,1:x -> abc|x.
Constraints
- 1 <= lines <= 10^4
- words are not empty and have no spaces
Examples
Input
abc x
Output
3:abc,1:x -> abc|x
Solutions
A length prefix tells the reader exactly how much to read, so any character may appear inside a word. This is the idea behind many binary protocols and formats (for example Redis, Protocol Buffers and netstrings). Delimiter-only formats break when the data contains the delimiter.
/*
* Problem : Process lines.
* Input : Several lines.
* Output : Encoded and decoded text.
* Approach: Words per line.
* Time : O(n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String[] lines) {
String[] output = new String[lines.length];
for (int i = 0; i < lines.length; i++) {
// Step 1: Encode. Write the length of each word, a colon and the word. Join the pieces with commas.
StringBuilder encoded = new StringBuilder();
for (String word : lines[i].split(" ")) {
if (encoded.length() > 0) {
encoded.append(',');
}
encoded.append(word.length()).append(':').append(word);
}
String text = encoded.toString();
// Step 2: Decode. Read the number up to the colon, then take exactly that many characters.
java.util.List<String> words = new java.util.ArrayList<>();
int position = 0;
while (position < text.length()) {
int colon = text.indexOf(':', position);
int length = Integer.parseInt(text.substring(position, colon));
words.add(text.substring(colon + 1, colon + 1 + length));
// Step 3: Skip the word and the comma after it.
position = colon + 1 + length + 1;
}
output[i] = text + " -> " + String.join("|", words);
}
return output;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
java.util.List<String> all = new java.util.ArrayList<>();
while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (!line.isEmpty()) {
all.add(line);
}
}
String[] lines = all.toArray(new String[0]);
System.out.println(String.join("\n", solve(lines)));
}
}
Hints (1)
- Why does splitting the encoded text on commas fail for the word c,d?