Encode and Decode Strings - Leetcode 271 - Python

0:00 - Read the problem
1:47 - Drawing Explanation
7:04 - Coding Explanation

leetcode 271

#sorted #array #python

[digestable_bits]

for those wondering why we can't just use a single digit number to delimit and track the length of the following word, what if word length >9 and takes up double digits! (maybe only my slow brain was confused about this :) )

[awesomebearaudiobooks]

Some people say that LeetCode problems are "useless exercises that real coders never use in their day-to-day job", but, honestly, this one seems quite ueseful. Yes, we are probably never going to be implementing encoding\decoding ourselves, but knowing how it works is a great thing, I think.

[TCErnesto]

great solution! just a note, the `encode` method is O(n**2) because string concatenation copies the entire string, so the result string is being copied over and over n times.

To make it O(n), we can use a list to mock a string builder. Each element of the list will be the delimiter and the word. At the end of the method we will join the list into a string and return it:

def encode(self, strs) -> str:
# O(n)
return ''.join(
f'{len(string)}#{string}'
for string in strs
)

in the code instead of using a list we can just use a generator of the encoded strings

[siqb]

Pretty damn good.

If you think about it that is kind of how UTF8 encoding works. The byte representations always *start* with a particular pattern indicating what is the first byte of a representation. If a character is represented by 4 bytes than the the other 3 also have a distinct pattern to show they belong to the first byte together.

[hugovinhal]

What if one of the strings happens to have a number followed by the #. Wont that break the decode?

[clintondannolfo]

This question is weird, but a good alternate solution would be to just store the comma separated length of items at the start of the string before a delimiter. Could also use base 16 numbers to save storage space.

[iltenahmet]

Another approach is we put "#" between every word and then another "#" if we have "#" inside the word. When we're decoding, if we have a single "#", it means it separates the word, however if there's another "#" next to it, it means it was inside a word.

[DragonStoneCreations]

I thought of escaping the delimter (like #) presnt within the string. but your solution is a simple and fast!

[iwormix]

I'm sure that on the actual interview this would not be a valid solution (or maybe?), but we can split / join by some non-printable ascii character, 0x01 is great
class Solution:
def encode(self, strs): return '\x01'.join(strs)
def decode(self, string): return string.split('\x01')

[vatsalsharma]

Waiting for your videos daily❤️
Can you also make a video on rat in a maze (but it is not on leetcode) as it also frequently asked question?

Edited : After seeing your some of the backtracking videos I’ve solved that problem.

[nickbunich]

Convert string size to byte array and put it into the encoded string, you don't need separator and you will use less space. But that also works!

[alejandroolaria]

Hey thank you very much for your content! which is the time complexity for your encoder example? I came out with something like O(M.N) M being the number of words within encoded string and N being the average length of the string. is this correct?

[anupkmr]

Java version :

public class Solution {
/*
* @param strs: a list of strings
* @return: encodes a list of strings to a single string.
*/
public static String encode(List<String> strs) {
StringBuilder result = new StringBuilder();
for(String s : strs){

}
return result.toString();

}

/*
* @param str: A string
* @return: dcodes a single string to a list of strings
*/
public static List<String> decode(String str) {
// Write your code here
List<String> ans = new ArrayList<>();
StringBuilder item = new StringBuilder();
int i = 0;
int j;
while (i < str.length()) {
j = i;
while(str.charAt(j) != '#'){
j++;
}
int wordLength = Integer.valueOf(str.substring(i, j));
int startIndex = j+1; // skipping number+# characters length
String subStr = str.substring(startIndex, wordLength+startIndex);
ans.add(subStr);
i = wordLength+startIndex;
}
return ans;
}
}

[sidazhong]

I originally thought that the fixed-length md5(s) hash could be used as the delimiter, because the result of the hash and the possibility of repeated characters in srts are almost zero.

[pieter]

Doesn't this solution depend on none of the strings containing multiple sequences of digit#? e.g. 3#3#3#3#?
in which case you wouldn't know which is the delimeter.

[ballakobe]

This reminds me of my class on Networking. Bit data is sent with headers, to help the recipient make sense of the data.

[siddharthmanumusic]

Could we not skip the delimiter using an escape character? If we found #, we could replace that with \#

[liamsism]

Wouldn't the time complexity for decode be O(nm) because we also slice a string?

[xlgznwf]

So I'm a little confused by this approach. Why would you go through the effort of saving the variable length in a number instead of just separating the words with a unique delimeter then using like '<delim>'.join(s for s in strs) and s.split('<delim>')?

[jffrysith]

Really interesting solution, my first thought was to use ordinals to map all the letters to their ordinal, then split each letter by a delimeter and each word by a delimeter, but this is a much faster solution lol.