Teaching Kids Programming: Videos on Data Structures and Algorithms
Yesterday, we talked about RunLength Decoding: Teaching Kids Programming – Run-Length Decoding/Decompression Algorithm.
Run-Length Encoding/Compression Algorithm in Python
Run-Length encoding is the reverse of the decoding/decompression process. We need to scan the characters by characters, and if current character is same as previous, we need to increment the counter, otherwise we append the previous counter and character pair to the result.
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution: def solve(self, s): assert len(s) > 0 ans = [] c = 1 for i in range(1, len(s)): if s[i - 1] == s[i]: c += 1 else: ans += str(c) + s[i - 1] c = 1 ans += str(c) + s[-1] return "".join(ans) |
class Solution:
def solve(self, s):
assert len(s) > 0
ans = []
c = 1
for i in range(1, len(s)):
if s[i - 1] == s[i]:
c += 1
else:
ans += str(c) + s[i - 1]
c = 1
ans += str(c) + s[-1]
return "".join(ans)We can use the groupby function to achieve one-liner implementation of Run-Length encoding algorithm:
1 2 3 | class Solution: def solve(self, s): return "".join(str(len(list(b))) + a for a, b in groupby(s)) |
class Solution:
def solve(self, s):
return "".join(str(len(list(b))) + a for a, b in groupby(s))–EOF (The Ultimate Computing & Technology Blog) —
Last Post: Teaching Kids Programming - Run-Length Decoding/Decompression Algorithm
Next Post: Teaching Kids Programming - Top Down and Bottom Up Dynamic Programming Algorithm to Type N letters on a 2-keys Keyboard