EncodeDecode Strings

All credits to the question go to Neetcode.io. I am merely borrowing from him.

Link - Neetcode 150

Approach 1

For encode:

    Parse string and encode in the format 
    `prefix` + `count` + `original string`

For decode:

    Parse string and decode 
    Check for presence of prefix
        Check for the next digit/set of digits for count
        Get the string

• This didn't actually work out for the reason that its difficult to work with this setup
  • first you search for the prefix
  • then you search for the count
    This is where it kinda gets fucked up because
  • count can be 1,2,3..n number of digits
  • how do you identify this when # is a part of the text itself (Ex. #55#xyz means I want 5 chars after the # but this would give me 55 characters and not really easy to build for this)

Approach 2

For encode:

    Parse string and encode in the format 
     `count` + `prefix` + `original string`

For decode:

    Parse string linearly with current pointer
        Check for presence of prefix in a loop and keep track of index
        
        Get the count by slicing the string until prefix index and current pointer
        Get the word by slicing string
        repeat

Code

def encode(self, strs: List[str]) -> str:

        final_str = ""
        prefix = "#"
        for word in strs:
            word_len = len(word)
            encoded_word = str(word_len) + prefix + word
            final_str+=encoded_word
        # print(final_str)
        return final_str

    def decode(self, s: str) -> List[str]:
        
        decoded_string = list()
        i = 0 
        j = 0
        while i < len(s):
            while s[j] != "#":
                j+=1
            
            count = int(s[i:j])
            start = j+1
            end = start+count

            word = s[start: end]
            decoded_string.append(word)

            i = end
            j=i
        return decoded_string

This logic fixes our previous issue because now, we know the count of characters already and the # just indicates where the word begins so we can ignore any subsequent #'s and directly obtain our slice.