LeetCode-Solutions/Python/string-compression.py at master · Monika-R/LeetCode-Solutions · GitHub

28 lines (26 loc) · 880 Bytes

# Time: O(n)

# Space: O(1)

class Solution(object):

def compress(self, chars):

"""

:type chars: List[str]

:rtype: int

"""

anchor, write = 0, 0

for read, c in enumerate(chars):

if read+1 == len(chars) or chars[read+1] != c:

chars[write] = chars[anchor]

write += 1

if read > anchor:

n, left = read-anchor+1, write

while n > 0:

chars[write] = chr(n%10+ord('0'))

write += 1

n /= 10

right = write-1

while left < right:

chars[left], chars[right] = chars[right], chars[left]

left += 1

right -= 1

anchor = read+1

return write

Expand file tree