Encode and decode strings

XXX. Encode and Decode Strings

String Manipulation

Custom Delimiter

Problem Statement:

Design an algorithm to encode a list of strings to a single string. The encoded string should be such that it can be decoded back into the original list of strings.

Use a custom delimiter approach:

• Replace all hashes (#) in the original strings with double hashes (##).
• Separate strings in the list with the delimiter " # " (hash surrounded by spaces).

Algorithm:

Encoding:

1. Initialize an empty string builder.
2. Iterate through each string in the input list:
• Replace all occurrences of # with ## in the string.
• Append the modified string to the builder, followed by the delimiter " # ".
3. Return the resulting string.

Decoding:

1. Split the encoded string by the delimiter " # ", including trailing empty strings.
2. Iterate through all elements except the last (empty string):
• Replace all occurrences of ## with # to reconstruct the original strings.
• Add the reconstructed strings to the result list.
3. Return the list of reconstructed strings.

Complexity:

Time Complexity: O(n), where n is the total number of characters in the input list. Each character is processed once during encoding and decoding.
Space Complexity: O(n), for the encoded string and the decoded list of strings.

Java Implementation:

import java.util.*;

public class Codec {
    // Encodes a list of strings to a single string.
    public String encode(List strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs)
            sb.append(s.replace("#", "##")).append(" # ");
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List decode(String s) {
        List strs = new ArrayList<>();
        String[] array = s.split(" # ", -1);
        for (int i = 0; i < array.length - 1; ++i)
            strs.add(array[i].replace("##", "#"));
        return strs;
    }
}