5
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ print(asciiencode('HelloWorld')) doesn't work at all! \$\endgroup\$ – 200_success Apr 21 '19 at 19:51
  • \$\begingroup\$ 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 \$\endgroup\$ – A.Lee Apr 21 '19 at 20:01
  • \$\begingroup\$ Sorry for the misunderstanding. I would have expected the decoding function to be called asciidecode() instead. \$\endgroup\$ – 200_success Apr 21 '19 at 20:10
  • \$\begingroup\$ i see. wil update my code \$\endgroup\$ – A.Lee Apr 21 '19 at 20:37
5
+50
\$\begingroup\$
  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
\$\endgroup\$
  • \$\begingroup\$ so what is time complexity? \$\endgroup\$ – A.Lee Apr 24 '19 at 18:50
  • \$\begingroup\$ @A.Lee When did you or I say anything about time complexity? \$\endgroup\$ – Peilonrayz Apr 24 '19 at 18:56
  • \$\begingroup\$ i mean for your while loop solution what is time complexity? O(2 ^ n)? \$\endgroup\$ – A.Lee Apr 24 '19 at 19:00
  • \$\begingroup\$ @A.Lee You've not answered my question. \$\endgroup\$ – Peilonrayz Apr 24 '19 at 19:01
  • \$\begingroup\$ 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 \$\endgroup\$ – A.Lee Apr 24 '19 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.