Reverse Words in a String II -- JAVA solution


  • 0
    M

    Algorithm:

    1. First, reverse the entire string. That will reverse the order of words. However, individual word's letter is also reversed. Example "the sky is blue" will change to "eulb si yks eht"
    2. Second, reverse the letter orders for individual words. After this step, the words' letters will be in the correct position. "blue is sky the"
    class Solution {
        public void reverseWords(char[] str) {
           //reverse the whole string
            reverse(str, 0, str.length-1);
    
           //reverse individual words letters.
            int startPos = 0;
            int endPos = 0;
            while(endPos<str.length-1) {
                if(str[++endPos] == ' ') {
                    reverse(str, startPos, endPos-1);
                    startPos = endPos+1;
                    endPos++;
                }
            }
            reverse(str, startPos, endPos); // reverse the last word
        }
        private void reverse(char[] str, int startPos, int endPos) {
            while(startPos < endPos) {
                char temp = str[startPos];
                str[startPos] = str[endPos];
                str[endPos] = temp;
                startPos++;
                endPos--;
            }    
        }
    }
    

Log in to reply
 

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