Encode and Decode Strings

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 encode and decode methods.

Example:
Input: [“lint”, “code”, “love”, “you”]
Output (Encoded): “4#lint4#code4#love3#you”
Output (Decoded): [“lint”, “code”, “love”, “you”]

Note: This is a LeetCode Premium problem, often found on LintCode for free.

Approach: Length Prefixing (Chunked Transfer)

We cannot simply use a special delimiter (like # or ,) to join the strings because the original strings themselves might contain that delimiter! If the input is ["hello#world", "test"], a simple join would result in "hello#world#test", making it impossible to know where the actual string boundaries are during decoding.

To solve this, we prefix each string with its length, followed by a delimiter (like #). This tells the decoder exactly how many characters to read for the string, allowing the string itself to safely contain any characters, including # or numbers.

Encoding Steps:

1. Initialize an empty string or array to build the result.
2. For every string in the input array, append its length, a # delimiter, and the string itself.
3. E.g., "lint" becomes "4#lint".

Decoding Steps:

1. Use a pointer i starting at 0 to traverse the encoded string.
2. While i is less than the string length:
   • Find the next # character starting from i. Let’s call its index j.
   • The substring from i to j is the integer length of the string.
   • The actual string starts immediately after the # (at j + 1) and ends at j + 1 + length.
   • Extract the substring, add it to your result array, and jump the i pointer to j + 1 + length to process the next string.

Solution

class Solution {
    /**
     * @param {string[]} strs
     * @returns {string}
     */
    encode(strs) {
        let res = "";
        for (let s of strs) {
            res += s.length + "#" + s;
        }
        return res;
    }

    /**
     * @param {string} str
     * @returns {string[]}
     */
    decode(str) {
        const res = [];
        let i = 0;
        
        while (i < str.length) {
            let j = i;
            // Find the delimiter '#'
            while (str[j] !== '#') {
                j++;
            }
            
            // Extract the length prefix
            const length = parseInt(str.substring(i, j));
            
            // Extract the actual string
            const word = str.substring(j + 1, j + 1 + length);
            res.push(word);
            
            // Move pointer to the start of the next encoded string
            i = j + 1 + length;
        }
        
        return res;
    }
}

Complexity Analysis

• Time Complexity: $O(n)$ for both encode and decode, where $n$ is the total number of characters across all strings. We touch every character essentially once.
• Space Complexity: $O(1)$ auxiliary space for both methods, although the returned encoded string or decoded array will take $O(n)$ space.