cc150：字元串：1.5

題目

利用字元重複出現的次數，編寫一個方法，實作基本的字元串壓縮功能，“aabccccaaa”變成“a2b3c4a3”。如果壓縮後字元串長度沒有變短，則傳回原型的字元

算法(c++)

https://github.com/zhoulike/algorithms/blob/master/cc150/1.5.cpp

算法

https://www.snip2code.com/Snippet/253088/CC150-1-5-Compress-String

複雜度:O(N),

/*import java.util.*;

class Solution{
public  static void main(String[] args)
}*/

import java.util.*;

class Solution{
    public static String compress(String str){

        //檢查壓縮後字元串是否會變長
        int size=countCompression(str);
        if(size>=str.length())
            return str;

        StringBuilder mystr=new StringBuilder();
        char last=str.charAt();
        int count=;

        for(int i=;i<str.length();i++){
            if(str.charAt(i)==last)  //找到重複字元
            {
                count++;
            }else//插入字元數目，更新last字元
            {
                mystr.append(last);
                mystr.append(count);
                last=str.charAt(i);
                count=;
            }
        }

        //需要單獨處理尾部的字元串
        System.out.println("last:"+last);
        System.out.println("count:"+count);
        mystr.append(last);
        mystr.append(count);
        return mystr.toString();

    }

    public static int countCompression(String str){
        if(str==null || str.length()==)
            return ;
        char last=str.charAt();
        int size=;
        int count=;
        for(int i=;i<str.length();i++){
            if(str.charAt(i)==last)
                count++;
            else{
                last=str.charAt(i);
                size+=+String.valueOf(count).length();
                count=;

            }

        }

        size+=+String.valueOf(count).length();
        return size;
    }

    public static void  main(String[] args){
        String str_test="aabcccccaaa";
        String str_res=compress(str_test);
        System.out.print(str_res);

    }
}