java O(n) solution


  • 0
    J

    first I used str, then got TLE, then I used array int[], it's much faster!

        public int magicalString(int n) {
            if(n<=0) return 0;
            if(n<4) return 1;
            int sum =1;
            //let int[] reprents the str
            int[] prestr =new int[n];
            //first let str: 12
            prestr[0]=1;prestr[1]=2;
            //last occurrences index in the str
            int prelen = 1;
            //last two chars in the str
            int c1 = 1;
            int c2 = 2;
            //current char
            int c = 1;
           
            for(int i=2;i<n;i++){
                //char c1 = prestr.charAt(i-2);
                //char c2 = prestr.charAt(i-1);
                c = 1;
                if(c1==c2){//if last two char are same , then next one must be different;
                    if(c1==1){
                        c=2;
                    }
                }else{//if last occurrence is 2, then repeat last char c2
                    if(prestr[prelen]==2){
                        c=c2;
                    }else{//else repeat c1;
                        c=c1;
                    }
                    prelen++; // in this case, increase the index;
                }
                if(c==1) sum++;
                prestr[i] = c;
                //update c1,c2
                c1 =c2;
                c2 =c;
            }
            
            return sum;
        }
      
    }

Log in to reply
 

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