accepted O(N) java solution!


  • 0
    T
    class Solution {
        public int compress(char[] chars) {
            if(chars==null || chars.length<1){
                return 0;
            }   
            if(chars.length==1){
                return 1;
            }
            
            char pre = chars[0];
            int start = 1;
            int count = 1;
            int qStart = 1;
            
            
            for(int i=1;i<chars.length;i++){
                if(pre==chars[i]){
                    count++;
                    chars[qStart++] = chars[i]; 
                }else{
                    if(count==1){
                        chars[start++] = chars[i];
                        count = 1;
                        pre = chars[i];
                        qStart = start;
                        continue;
                    }
                    
                    String num = String.valueOf(count);
                    if(num.length()+start<=qStart){
                        for(int j=0;j<num.length();j++){
                            chars[start++] = num.charAt(j);
                        }
                        chars[start++] = chars[i];
                        qStart = start;
                    }else{
                        start=qStart;
                    }
                    count = 1;
                    pre = chars[i];
                }
            }
            
            if(count>=2){
                String num = String.valueOf(count);
                 if(num.length()+start<=qStart){
                        for(int j=0;j<num.length();j++){
                            chars[start++] = num.charAt(j);
                        }
                    }
            }
            
            return start;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.