Leetcode - String Compression

https://leetcode.com/problems/string-compression/

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

Follow up:
Could you solve it using only O(1) extra space?

Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

func compress(chars []byte) int {
    if len(chars) < 2 {
        return len(chars)
    }
    result := 0
    left := 0
    right := left+1
    for right < len(chars) {
        right = left+1
        for right < len(chars) && chars[right] == chars[left] {
            right++
        }
        if right == len(chars) {
            break
        }
        //fmt.Println("right - left: ", right - left)
        chars[result] = chars[left]
        if right - left == 1 {
            left = right
            result++
            continue
        }
        if left + 1 < len(chars) {
            count := getCounts(right - left)
            for i := 1; i < len(count)+1; i++ {
                chars[result+i] = count[i-1]
            }
            
            result += 1 + len(count)
            left = right
        }
    }
    
    chars[result] = chars[left]
    if right - left == 1 {
        result++
    } else {
        count := getCounts(right - left)
        for i := 1; i < len(count)+1; i++ {
            chars[result+i] = count[i-1]
        }
        result += 1 + len(count)
    }
    
    
    
    return result
}

func getCounts(num int) []byte {
    result := []byte{}
    for num > 0 {
        result = append(result, byte(num%10+'0'))
        num /= 10
    }
    for i := 0; i < len(result)/2; i++ {
        result[i], result[len(result)-i-1] = result[len(result)-i-1], result[i]
    }
    return result
}

• 相关文章
• 全局相关文章