Encode and Decode Strings medium

Problem Statement

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Please implement the encode and decode methods.

Note:

The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.

Example 1:

Input: ["Hello", "World"] Output: ["Hello", "World"] Explanation: One possible encode method is: "Hello/World" You can use any character to split, but you must ensure that such character is not part of any string in the input list.

Example 2:

Input: ["We", "Are", "the", "Champions"] Output: ["We", "Are", "the", "Champions"] Explanation: One possible encode method is: "We/Are/the/Champions"

Steps

1. Encoding:

   • Choose a delimiter character that is unlikely to appear in the input strings. A common choice is a character that's not printable, like the null character (\0). However, using '/' for better readability in this example.
   • Concatenate the strings, separating them with the delimiter.

2. Decoding:

   • Split the encoded string using the delimiter.
   • Return the resulting list of strings.

Explanation

The key idea is to use a delimiter to separate the strings during encoding. The choice of delimiter is crucial. We need to ensure it doesn't clash with characters that might be present within the strings themselves. While \0 is a safe bet in many cases, using '/' is a more practical choice for readability during demonstration.

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        if (strs == null || strs.isEmpty()) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strs.size(); i++) {
            sb.append(strs.get(i));
            if (i < strs.size() - 1) {
                sb.append("/"); //Using '/' as delimiter
            }
        }
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        if (s == null || s.isEmpty()) {
            return new ArrayList<>();
        }
        return Arrays.asList(s.split("/"));
    }

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


        strs = Arrays.asList("We", "Are", "the", "Champions");
        encoded = codec.encode(strs);
        decoded = codec.decode(encoded);
        System.out.println("Encoded: " + encoded);
        System.out.println("Decoded: " + decoded);
    }
}

Complexity

• Time complexity:

  • encode: O(N), where N is the total number of characters in all strings.
  • decode: O(N), where N is the length of the encoded string. String.split has linear time complexity.

• Space complexity:

  • encode: O(N), to store the encoded string.
  • decode: O(M), where M is the number of strings in the decoded list. This space is needed to store the resulting list.