简单字符串压缩算法 [英] Algorithm for simple string compression

问题描述

我想以以下形式找到字符串的最短编码:

abbcccc = a2b4c

解决方案

下面是我的C ++实现，以O(n)时间复杂度和O(1)空间复杂度就地完成它.

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = (int)chars.size();
        if(chars.empty()) return 0;
        int left = 0, right = 0, currCharIndx = left;
        while(right < n) {
            if(chars[currCharIndx] != chars[right]) {
                int len = right - currCharIndx;
                chars[left++] = chars[currCharIndx];
                if(len > 1) {
                    string freq = to_string(len);
                    for(int i = 0; i < (int)freq.length(); i++) {
                        chars[left++] = freq[i];
                    }
                }
                currCharIndx = right;
            }
            right++;
        }
        int len = right - currCharIndx;
        chars[left++] = chars[currCharIndx];
        if(len > 1) {
            string freq = to_string(len);
            for(int i = 0; i < freq.length(); i++) {
                chars[left++] = freq[i];
            }
        }
        return left;
    }
};

您需要跟踪三个指针-right用于迭代，currCharIndx用于跟踪当前字符的第一位置，left用于跟踪压缩字符串的写入位置.

I would like to find the shortest possible encoding for a string in the following form:

abbcccc = a2b4c

解决方案

Following is my C++ implementation to do it in-place with O(n) time complexity and O(1) space complexity.

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = (int)chars.size();
        if(chars.empty()) return 0;
        int left = 0, right = 0, currCharIndx = left;
        while(right < n) {
            if(chars[currCharIndx] != chars[right]) {
                int len = right - currCharIndx;
                chars[left++] = chars[currCharIndx];
                if(len > 1) {
                    string freq = to_string(len);
                    for(int i = 0; i < (int)freq.length(); i++) {
                        chars[left++] = freq[i];
                    }
                }
                currCharIndx = right;
            }
            right++;
        }
        int len = right - currCharIndx;
        chars[left++] = chars[currCharIndx];
        if(len > 1) {
            string freq = to_string(len);
            for(int i = 0; i < freq.length(); i++) {
                chars[left++] = freq[i];
            }
        }
        return left;
    }
};

You need to keep track of three pointers - right is to iterate, currCharIndx is to keep track the first position of current character and left is to keep track the write position of the compressed string.

这篇关于简单字符串压缩算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！