LeetCode Diaries #5: I Put a Number in Front of My String and Called It a Day

Let us just hope our private information is not being encoded in the way I solved today’s problem.

The question itself doesn’t give you much to work with since you can encode the string in any which way and just reverse engineer it in the decoding method. These are two of my approaches to the problem.

Question:

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.

Machine 1 (sender) has the function:

String encode(List<String> strs) {
    // ... your code
    return encoded_string;
}

Machine 2 (receiver) has the function:

List<String> decode(String encoded_string) {
    // ... your code
    return decoded_strs;
}

So Machine 1 does:

String encoded_string = encode(strs);

and Machine 2 does:

List<String> decoded_strs = decode(encoded_string);

decoded_strs in Machine 2 should be the same as the input strs in Machine 1.

Implement the encode and decode methods.

Constraints:

• 0 <= strs.length < 100
• 0 <= strs[i].length < 200
• strs[i] contains any possible characters out of 256 valid ASCII characters.

1. Straightforward Approach

The most basic approach I came up with for the encode method was to take each string in the list and first write its length, followed by a separating character, and then the string itself. Similarly, to decode it I walked through the combined string with a pointer ‘i’. First I read characters until I hit ‘’ — that gave me the size as a string, which I converted to an int. I skipped past the ‘’ (i += 1), then sliced out exactly size characters as the next string, appended it to the result, and moved ‘i’ past that slice. I repeated this until ‘i’ reached the end of ‘s’.

Visualisation of the straight forward approach

Converting this into code we get:

def encode(self, strs: List[str]) -> str:
        s = ''
        for i in strs:
            size = str(len(i))
            s += size + '*' + i
        return s
def decode(self, s: str) -> List[str]:
        i = 0
        r = []
        while i<len(s):
            size = ''
            while s[i] != '*':
                size += s[i]
                i +=1
            size = int(size)
            i = i+1
            r.append(s[i: i+size])
            i = i + size
        return r

This gives us a time and space complexity of O(m) where ‘m’ is the total input length (sum of lengths of all strings).

2. Encoding with Commas Approach

In this version, I separated the encoded string into two parts: a header of comma-separated lengths capped by ‘’, then a body of all characters concatenated together. To encode the strings, I used two loops: the first wrote the length of each string followed by a comma, then appended a single ‘’ as the header terminator once it finished; the second loop appended the raw characters of every string with nothing in between. Similarly, to decode the string I used two loops: one that read digits up to each comma, converted them into integers, and collected them into a size array — stopping once it hit ‘*’ — and a second that, for each size in the size array, sliced out that many characters from the body and advanced the iterator by that amount.

Visualisation of commas approach

The code for this would be:

def encode(self, strs: List[str]) -> str:
        s = ''
        for i in strs:
            sz = str(len(i))
            s += sz + ','
        s += '*'
        for i in strs:
            s += i
        return s
def decode(self, s: str) -> List[str]:
        i = 0
        sz=[]
        r = []
        while s[i]!='*':
            c = ''
            while s[i] != ',':
                c += s[i]
                i +=1
            c = int(c)
            sz.append(c)
            i +=1
        i += 1
        for j in sz:
            r.append(s[i:i+j])
            i +=j
        return r

This approach gives us a time and space complexity of O(m+n) where ‘m’ is the sum of lengths of all the strings and ‘n’ is the number of strings.

One tradeoff worth noting: this version does two passes over strs during encode, and needs an extra list during decode, whereas the ‘*’-per-string version does it in one pass with no extra list. Functionally they're equivalent and both handle strings containing digits, commas, or asterisks correctly, since the delimiter positions are inferred from counted lengths, not from scanning the body itself.

So there you have it — two ways to smuggle a list of strings across a network without anyone noticing. Machine 1 whispers, Machine 2 listens, and somewhere in the middle a ‘*’ is quietly holding the whole operation together. If your bank is reading this: no, I will not be reviewing your encoding scheme for free. Everyone else — got a slicker way to encode a list of strings? Or did you just brute-force it with “”.join() and hope for the best? Tell me in the comments, I promise not to judge (much).