Example: Encode Decode Strings

Design an algorithm to encode and decode a list of strings.

Encoding:

You need to design a method that converts a list of strings into a single encoded string. The encoded string should be such that it can be uniquely decoded back into the original list of strings.

Decoding:

You need to design a method that converts the encoded string back into the original list of strings.

Constraints:

The encoded string should be such that each string can be retrieved accurately during decoding. You must handle cases where the strings themselves might contain special characters or delimiters used in the encoding scheme.

Solution

To encode and decode a list of strings, we need to develop a scheme that ensures the encoded string can be uniquely parsed back into the original list of strings. One common approach is to use a delimiter or length prefix to separate the strings in the encoded format.

Approach:

• Encoding: Use a length prefix followed by a special character (e.g., #) before each string to ensure that we can uniquely identify the boundaries of each string.
• Decoding: Parse the encoded string using the length prefix to correctly extract each string.

import java.util.*;

public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder encoded = new StringBuilder();
        for (String str : strs) {
            encoded.append(str.length()).append('#').append(str);
        }
        return encoded.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> decoded = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (s.charAt(j) != '#') {
                j++;
            }
            // preferred to valueOf because valueOf uses parseInt internally and then boxes it into an Integer.
            int length = Integer.parseInt(s.substring(i, j));
            String str = s.substring(j + 1, j + 1 + length);
            decoded.add(str);
            i = j + 1 + length;
        }
        return decoded;
    }

    public static void main(String[] args) {
        Codec codec = new Codec();
        List<String> strs = Arrays.asList("Hello", "World", "Encode", "Decode", "123#456", "");
        String encoded = codec.encode(strs);
        System.out.println("Encoded: " + encoded);
        List<String> decoded = codec.decode(encoded);
        System.out.println("Decoded: " + decoded);
    }
}