华为OD面试手撕算法-字符串压缩

题目描述

本题是leetcode原题：字符串压缩

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串"aabcccccaaa"会变为"a2b1c5a3"。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

思路分析

可以考虑使用滑动窗口解决。以"aabcccaaa"为例，指针遍历(部分)过程如下图

思路描述：

start,end指针表示滑动窗口的开始和结束位置，res表示最终的结果集，遍历过程中判断窗口开始和结束位置的元素值是否相等，则有以下两种情况：

①相等时：向后移动结束指针，扩大窗口范围；

②不相等时：将窗口大小，结束位置元素依次加入结果集；窗口开始指针指向结束指针，并向后移动结束指针；

代码实现

代码部分就不再赘述了哈，直接上Golang代码

func compressString(S string) string {
    //边界条件(eg:aa,ab)
    if len(S) <= 2 {
        return S
    }
    //解法1：双指针
    start,end := 0,1
    res := string(S[start])
    for end < len(S) {
        if S[end] != S[start]{
            //S[end] != S[start]时：将end-start+1放入结果集；将S[end]放入结果集；start指针指向end
            res += strconv.Itoa(end-start)
            res += string(S[end])
            start = end
        }
        end++
    }
    //将最后遍历元素添加到结果集
    res += strconv.Itoa(end-start)
    if len(res) < len(S){
        return res
    }
    return S
}