Encode and Decode a String

Given an array of strings s[], you are required to create an algorithm in the encode() function that can convert the given strings into a single encoded string, which can be transmitted over the network and then decoded back into the original array of strings. The decoding will happen in the decode() function.

You need to implement two functions:

1. encode(): This takes an array of strings s[] and encodes it into a single string.
2. decode(): This takes the encoded string as input and returns an array of strings containing the original array as given in the encode method.

Implementation#

The key challenge is choosing a delimiter that cannot appear inside the strings themselves. Using a single # character as a separator works here because decode simply scans character by character and splits on every # it encounters. Each string in the original array is appended to the encoded result followed by #, so the encoded form is deterministic and uniquely reversible. This runs in O(n) for both encode and decode where n is the total number of characters across all strings, with O(n) extra space for the encoded/decoded output.

class Solution {
  public:
    string encode(vector<string>& s) {
        string encodedString="";
        for(int i=0;i<s.size();i++){
            encodedString += s[i] + '#';
        }
        return encodedString;
    }

    vector<string> decode(string& s) {
        vector<string> decodedList;
        string tempStr = "";
        for(char c: s)
        {
            if(c=='#'){
                decodedList.push_back(tempStr);
                tempStr = "";
                continue;
            }
            tempStr += c;
        }
        return decodedList;
    }
};

Time Complexity:

• Encode: O(n)
• Decode: O(n)