Wednesday, February 03, 2016

compress, decompress string

compress(s):
    if s == null:
        throw "null"
    start = end = 0
    buffer = new
    while start < s.length():
        while end < s.length() && s[end] == s[start]:
            end++
        count = end - start
        buffer.append(s[start] + count)
        start = end
    return buffer.length() >= s.length() ? s : buffer.tostring()
[Hat tip to SE]

Few optimizations:
- If s has digits, return itself.
- If buffer's length equals or exceeds s' length, break.
- Append count only if 2+.
compress(s):
    if s == null:
        throw "null"
    for i = 0, i < s.length(), i++:
        if 0 <= (s[i] - '0') <= 9:
            return s
    start = end = 0
    buffer = new
    while start < s.length():
        while end < s.length() && s[end] == s[start]:
            end++
        count = end - start
        buffer.append(s[start])
        if count > 1:
            buffer.append(count)
        if buffer.length() >= s.length():
            break
        start = end
    return buffer.length() < s.length() ? buffer.tostring() : s
Decompress.
decompress(s):
    if s == null:
        throw
    buffer = new
    i = 0
    while i < s.length():
        c = s[i]
        dstart = dend = i+1
        while dend < s.length() && 0 <= (s[dend]-'0') <= 9:
            dend++
        count = max(1, count(s, dstart, dend))
        buffer.append(repeat(c, count))
        i = dend
    return buffer.tostring()

count(s, start, end):
    if start >= end || start >= s.length() || end > s.length():
        return 0
    return int.parse(s.substring(start, end-start))

repeat(c, count):
    buffer = new (capacity: count)
    for i = 0, i < count, i++:
        buffer.append(c)
    return buffer.tostring()

No comments:

Post a Comment