Easy to understand Java solution with explanatoin


  • 1
    R

    The idea is that each time we want to work on an interval that is 2k long. If the ending position of the 2k interval fits in the char array, we work on the 2k interval (i.e. reverse the first k chars). After we're done with the current 2k interval, we move on to the next 2*k interval until the interval doesn't fit in the array anymore. In that case, the last position of the interval to be worked on is Math.min(endPos+k-1, sa.length-1).

    public String reverseStr(String s, int k) {
            if (s == null || s.length() ==0 || k<=0){
                return s;
            }
            char[] sa = s.toCharArray();
            int endPos = 2*k-1;
            while (endPos <= sa.length-1 ){
                reverse(endPos-2*k+1, endPos-k, sa);
                endPos += 2*k;
            }
            // doesn't fit anymore, move endPos to the previous endPos+1 and this will be the starting position of the last interval
            endPos = endPos - 2*k + 1;
            reverse(endPos, Math.min(endPos+k-1, sa.length-1), sa);
            return new String(sa);
        }
        
        private void reverse(int start, int end, char[] sa){
            while (start < end){
                char temp = sa[start];
                sa[start] = sa[end];
                sa[end] = temp;
                start++;
                end--;
            }
        }
    

Log in to reply
 

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