makispaiktis

DCP29 - AAAABBBCCD

Sep 28th, 2020
893
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2. This problem was asked by Amazon.
  3. Run-length encoding is a fast and simple method of encoding strings. The basic idea is to represent repeated successive characters as a single count
  4. and character. For example, the string "AAAABBBCCDAA" would be encoded as "4A3B2C1D2A".
  5. Implement run-length encoding and decoding. You can assume the string to be encoded have no digits and consists solely of alphabetic characters.
  6. You can assume the string to be decoded is valid.
  7. '''
  8. from timeit import default_timer as timer
  9.  
  10. def solve(message):
  11.     n = len(message)
  12.     letters = list()
  13.     letters.append(message[0])
  14.     counters = list()
  15.     counters.append(1)
  16.     for i in range(1, n):
  17.         if message[i] == letters[len(letters)-1]:
  18.             counters[len(counters)-1] += 1
  19.         else:
  20.             letters.append(message[i])
  21.             counters.append(1)
  22.  
  23.     # Now, I have to create the returned string based on the 2 lists
  24.     result = ""
  25.     if len(letters) != len(counters):
  26.         print("Error using function 'solve'.")
  27.         return -1000
  28.     for i in range(len(letters)):
  29.         result += (str(counters[i]) + letters[i])
  30.     return result
  31.  
  32. def prettyPrint(message):
  33.     start = timer()
  34.     result = solve(message)
  35.     end = timer()
  36.     elapsed = 10**6 * (end - start)
  37.     print(message + " ----> " + str(result) + " (" + str(round(elapsed, 2)) + " μs)")
  38.  
  39.  
  40. # MAIN FUNCTION
  41. print()
  42. messages = ["AAAAAAAAAKK", "AAAABBBCCDAA", "AAABBBaaabbbAAA", "asdfQWE"]
  43. for message in messages:
  44.     prettyPrint(message)
RAW Paste Data