想问一道Google 常考的压缩字符串题目

aabbbcc 压缩成 a*2b*3c*2，再解压缩原来的字符串里可能也有数和*

我想过 把字符串里原本的* 前面加一个井号 但是 这么一加 井号可能就压缩不了了。 对于数字 比如说 2aaab 这样直接压缩的话23*ab可能就会变成23个a 在解析的时候 不知道大家有没有好思路

练习一下，补上代码：
    String compress(String s) {
        StringBuilder sb = new StringBuilder();
        if (s == null || s.length() == 0) {
            return "";
        }
        char curChar = s.charAt(0);
        sb.append(curChar).append('*');
        int curLen = 1;
        for(int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == curChar) {
                curLen++;
            } else {
                sb.append(curLen);
                curChar = s.charAt(i);
                sb.append(curChar).append('*');
                curLen = 1;
            }
        }
         sb.append(curLen);
         return sb.toString();
    }
   
    String decompress(String s) {
        StringBuilder sb = new StringBuilder();
        if (s == null || s.length() == 0) {
            return "";
        }
        for(int i = s.length() - 1; i >= 0; i--) {
            int num = 0;
            int base = 1;
            while(s.charAt(i) != '*') {
                num += Integer.parseInt(s.charAt(i)) * base;
                base *= 10;
                i--;
            }
            i--;//此时i指向要恢复的字符
            char curChar = s.charAt(i);
            for(int j = 0; j < num; j++) {
                sb.append(curChar);
            }
        }
        return sb.reverse().toString();
    }

压缩比较容易。解压的话可以倒着来，比如a*2b*3c*2, 从后往前读直到遇到第一个星号，说明有2个c，然后直到字符串首

yueliu2366 发表于 2016-4-27 05:54
压缩比较容易。解压的话可以倒着来，比如a*2b*3c*2, 从后往前读直到遇到第一个星号，说明有2个c，然后直到 ...

对于数字呢 比如说3aaa=33*a这样就有歧义了

陈润鹏 发表于 2016-4-27 09:14
对于数字呢 比如说3aaa=33*a这样就有歧义了

是不是我题意理解错了？ 给的例子aabbbcc 压缩成 a*2b*3c*2，是不是说源字符串压缩成 “字符*个数”这种形式的？如果是这样3aaa不是应该压缩成3*1a*3吗？

yueliu2366 发表于 2016-4-27 09:53
是不是我题意理解错了？ 给的例子aabbbcc 压缩成 a*2b*3c*2，是不是说源字符串压缩成 “字符*个数”这种 ...

这样的压缩 有时候却起不到压缩效果  就想问 有没有更好的判断方式 比如说有一些就不压缩。 3a2*a这样要更优一点

陈润鹏 发表于 2016-4-27 10:15
这样的压缩 有时候却起不到压缩效果  就想问 有没有更好的判断方式 比如说有一些就不压缩。 3a2*a这样要 ...

哦，你意思是题目并没有要求压缩成什么指定的格式，只要自己设计一个压缩函数，一个解压函数就可以了？

yueliu2366 发表于 2016-4-27 10:46
哦，你意思是题目并没有要求压缩成什么指定的格式，只要自己设计一个压缩函数，一个解压函数就可以了？

大致follow这个idea就好

yueliu2366 发表于 2016-4-27 09:53
是不是我题意理解错了？ 给的例子aabbbcc 压缩成 a*2b*3c*2，是不是说源字符串压缩成 “字符*个数”这种 ...

3aaa 没歧义但是aaa...3有歧义吧

renli3000 发表于 2016-4-27 11:19
3aaa 没歧义但是aaa...3有歧义吧

没问题 是我想错了