ASCII code decode to string

Question

I am working on this question and have my answer as following?

A string is encoded by performing the following sequence of actions:

1. Replace each character with its ASCII value representation.
2. Reverse the string.

For example, the table below shows the conversion from the string "HelloWorld" to the ASCII string "7210110810811187111114108100":

Character
H e l l o W o r l d
ASCII Value
72 101 108 108 111 87 111 114 108 100

The ASCII string is then reversed to get the encoded string "0018014111117811180180110127".

The characters in encoded string are within the range 10 - 126 which include special characters.

Example:
asciidecode('111111') => '\x0b\x0b\x0b' or 'oo'
because we can split the input 111111 (after reverse back: '111111') like 11,11,11 or 111,111

from typing import List
def asciidecode(self, s: str) -> List:
 if not s: return ''
 s = s[::-1]
 n = len(s)
 ch_map = {str(i): chr(i) for i in range(10, 127)}
 dp = [[''] for _ in range(n + 1)]
 dp[2] = [ch_map[s[:2]]] if s[:2] in ch_map else ''
 dp[3] = [ch_map[s[:3]]] if s[:3] in ch_map else ''
 dp[4] = [dp[2][0] + ch_map[s[2:4]]] if s[2:4] in ch_map else ''
 for i in range(5, n + 1):
 p1 = s[i - 2: i]
 p2 = s[i - 3: i]
 tmp = []
 if p1 in ch_map:
 tmp += [i + ch_map[p1] for i in dp[i - 2]]
 if p2 in ch_map:
 tmp += [i + ch_map[p2] for i in dp[i - 3]]
 dp[i] = tmp
 return dp[-1]

• 200_success: print(asciiencode('HelloWorld')) doesn't work at all!
• A.Lee: the question is input from a decode asciicode like "0018014111117811180180110127", need to write a function to get original string, but i will update question to make more clear
• 200_success: Sorry for the misunderstanding. I would have expected the decoding function to be called asciidecode() instead.
• A.Lee: i see. wil update my code

Answer 1

1. return '' doesn't have the type List.
2. List means List[Any], you should use List[str].

3. Your variable names are garbage.

   • s -> string
   • n -> length
   • ch_map -> char_map or character_map
   • dp -> what does this even mean?
   • p1 -> position_1?

4. Don't put return statements on the same line as an if.

5. Again strings shouldn't be assigend to lists, yes you can iterate over them because they're both sequences. But they're not the same type. [ch_map[s[:2]]] if s[:2] in char_map else ''
6. ch_map should be a constant outside the function.
7. It's far easier to understand your code if it's written using recursion.
8. Recursion has some problems, and so it should be written in a way that allows you to easily convert it to a while loop.

CHAR_MAP = {str(i): chr(i) for i in range(10, 127)}
def asciidecode(string: str) -> List[str]:
 if not string:
 return []
 string = string[::-1]
 length = len(string)
 def inner(index):
 if index == length:
 yield ''
 else:
 for size in (2, 3):
 if length < index + size:
 break
 letter = CHAR_MAP.get(string[index:index + size])
 if letter is not None:
 for word in inner(index + size):
 yield letter + word
 return list(inner(0))
def asciidecode_pre_while(string: str) -> List[str]:
 if not string:
 return []
 string = string[::-1]
 length = len(string)
 output = []
 def inner(index, word):
 if index == length:
 output.append(word)
 return
 for size in (2, 3):
 if length < index + size:
 break
 letter = CHAR_MAP.get(string[index:index + size])
 if letter is not None:
 inner(index + size, word + letter)
 inner(0, '')
 return output

From the second one it's easy to convert it to a while loop:

CHAR_MAP = {str(i): chr(i) for i in range(10, 127)}
def asciidecode(string: str) -> List[str]:
 if not string:
 return []
 string = string[::-1]
 length = len(string)
 output = []
 stack = [(0, '')]
 while stack:
 index, word = stack.pop()
 if index == length:
 output.append(word)
 continue
 for size in (2, 3):
 if length < index + size:
 break
 letter = CHAR_MAP.get(string[index:index + size])
 if letter is not None:
 stack.append((index + size, word + letter))
 return output

• A.Lee: so what is time complexity?
• Peilonrayz: @A.Lee When did you or I say anything about time complexity?
• A.Lee: i mean for your while loop solution what is time complexity? O(2 ^ n)?
• Peilonrayz: @A.Lee You've not answered my question.
• A.Lee: i do not think I mention anything about time complexity on my post but want to know what is it for your while loop solution