Encode And Decode Strings

Let’s try to solve the Leetcode problem https://leetcode.com/problems/encode-and-decode-strings/

Description

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(vector<string> strs) {
// … your code
return encoded_string;
}

Machine 2 (receiver) has the function:
vector<string> decode(string s) {
//… your code
return strs;
}
So Machine 1 does:
string encoded_string = encode(strs);
and Machine 2 does:
vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.
You are not allowed to solve the problem using any serialize methods (such as eval).

Example 1:
Input: dummy_input = ["Hello","World"]
Output: ["Hello","World"]
Explanation:
Machine 1:
Codec encoder = new Codec();
String msg = encoder.encode(strs);
Machine 1 ---msg---> Machine 2

Machine 2:
Codec decoder = new Codec();
String[] strs = decoder.decode(msg);
Example 2:
Input: dummy_input = [""]
Output: [""]

Constraints:

• 1 <= strs.length <= 200

• 1 <= strs[i].length <= 200

• strs[i] contains any possible characters out of 256 valid ASCII characters.

Solution

Aloha.

Based on the description, we understand that we need to encode and decode the string. Also, we know that letters in the string will be in ASCII characters. What if we add a delimiter as a non-ASCII character? Will it work? Yes, it will.

But your interview can give you a follow-up that we should use only ASCII characters. How can we solve it?

I will try to explain one of the possible solutions. I want to add a special character to each word and character count in this word.

For example, if we have “word” after encoding, it will look like “4#word”.

Yes, you are right. I’m using “#” as a special character. But what if our word starts with “#”, is it a problem for us? Sure nope. See, our base word is “###word###”. After encoding, it will look like 10####word###. And we know, that the first “#” is our delimiter, the characters behind it are the characters count of the word, and the next ten characters are our word.

Is it clear? Let’s deep dive and check code solution for this problem.

Code

    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String word : strs){
            sb.append(word.length());
            sb.append("#");
            sb.append(word);
        }
        return sb.toString();
    }

public List<String> decode(String str) {
        List<String> rez = new ArrayList<>();

        for(int i = 0; i < str.length(); i++){
            String substring = str.substring(i);
            int indexOf = substring.indexOf("#");
            int dig = Integer.parseInt(str.substring(i, i+ indexOf));
            i+= indexOf + 1;
            int cur = 0;
            StringBuilder sb = new StringBuilder();
            while (cur < dig){
                sb.append(str.charAt(i));
                i++;
                cur++;
            }
            rez.add(sb.toString());
            i--;
        }

        return rez;
    }