🌱 Keegan's Digital Garden

271. Encode and Decode Strings

2 min read

📝 Problem Details

build a function to encode a list of strings to a single string the encoded string is decoded back to the original list of strings

💭What Were My Initial Thoughts?

- key problem, once the strings are concatenated together, we are unable to decode / separate them at their correct length unless there is some sort of identifier

💡 Explanation of Solution

encode:
- iterate through the input list and convert each string into the format:
	- [length]#[string]
- the length tells us exactly how many characters belong to the string 
- the # is the delimiter that helps locate the length easily 
- the final encoded string is just a concatenation of all these formatted strings

decode:
- iterate through the encoded string while extracting each length
- using the length, we extract the corresponding string 
- move the pointer and repeat until all strings are extracted

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

💻 Implementation of Solution

class Codec {
public:
 
    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string result = "";
        for(const string& str : strs) {
            result += to_string(str.length()) + "#" + str;
        }
        return result;
    }
 
    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        vector<string> strs;
        int i = 0;
 
        while(i < s.length()) {
            int index = s.find('#', i);
            int len = stoi(s.substr(i, index - i));
            i = index + 1;  // Move past the '#'
            strs.push_back(s.substr(i, len));
            i += len;  // Move past the extracted string
        }
 
        return strs;
    }
};
 
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.decode(codec.encode(strs));

Graph View