Ac solution code


  • 0

    The basic idea are with two steps as follows:

        the sky is blue:
     1) eht yks si eulb <- Reverse each word
     2) blue is sky the <- Reverse the whole string
    

    Runtime complexity = O(n^2) for reversing each word + O(n) for resersing the whole string = O(n^2)

    public void reverseWords(char[] s) {  
    	if (s == null || s.length == 0) return; 
        int start = 0;
        for (int i = 0; i < s.length; i++) { 
        	if (s[i] == ' ' || i == s.length - 1) {// 1) Reverse each word
        		int end = (i == s.length - 1) ? i : i - 1;
        		reverseWord(s, start, end);        		
        		start = i + 1;
        	}
        }        
        reverseWord(s, 0, s.length - 1);// 2) Reverse the whole string
    }     
    void reverseWord(char[] s, int start, int end) {
    	while (start < end) {
    		char ch = s[start];
    		s[start++] = s[end];
    		s[end--] = ch;
    	} 
    }

Log in to reply
 

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