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:

encode("Hello", "World") == "Hello#World#" decode("Hello#World#") == ["Hello", "World"]

Example 2

Input: ["We", "are", "happy"]

Output: ["We", "are", "happy"]

Explanation:

encode("We", "are", "happy") == "We#are#happy#" decode("We#are#happy#") == ["We", "are", "happy"]

Steps

1. Encoding:

   • Iterate through the list of strings.
   • Concatenate each string with a delimiter (e.g., '#'). This delimiter should not be a character that can appear within the strings themselves. If such a character is guaranteed not to exist in the strings, it can be used. Otherwise, a more robust approach, like length-prefixed encoding is necessary.

2. Decoding:

   • Split the encoded string using the delimiter.
   • The resulting array will be the decoded list of strings.

Explanation

The solution uses a simple delimiter '#' to separate strings in the encoded string. This approach is straightforward and easy to understand. However, it has a limitation: if the delimiter character appears within one of the input strings, the decoding process will fail. A more robust solution would involve a length-prefix encoding scheme where the length of each string is included in the encoding. This removes the limitation of special characters.

Code

using System;
using System.Collections.Generic;
using System.Text;

public class Codec
{
    // Encodes a list of strings to a single string.
    public string encode(IList<string> strs)
    {
        StringBuilder sb = new StringBuilder();
        foreach (string str in strs)
        {
            sb.Append(str).Append("#");
        }
        return sb.ToString();
    }

    // Decodes a single string to a list of strings.
    public IList<string> decode(string s)
    {
        IList<string> res = new List<string>();
        string[] arr = s.Split('#');
        foreach (string str in arr)
        {
            if (str != "") // Handle trailing '#'
                res.Add(str);
        }
        return res;
    }
}

Complexity

Encoding:

• Time Complexity: O(N), where N is the total number of characters in all strings. We iterate through each character once.
• Space Complexity: O(N), The encoded string's size is proportional to the size of the input strings.

Decoding:

• Time Complexity: O(N), We iterate through the encoded string once to split it and again to iterate over the resulting array.
• Space Complexity: O(N), The decoded list of strings' size is proportional to the size of the encoded string.

Important Note: This solution assumes the '#' character is not present in the input strings. For a more robust solution that handles all possible characters, consider using a length-prefix encoding or a more sophisticated encoding scheme. This requires more complex code, but will be significantly more resilient.