LeetCode 151. Reverse Words in a String - (Problem: https://leetcode.com/problems/reverse-words-in-a-string) - Given an input string, reverse the string word by word. For example, Given s = "the sky is blue", return "blue is sky the". NOTES: A sequence of non-space characters constitutes a word. Remove all leading and trailing spaces. Reduce mul…

ReverseWordsInAString.java

/**
 * LeetCode 151. Reverse Words in a String (Problem Link: https://leetcode.com/problems/reverse-words-in-a-string)
 * Given an input string, reverse the string word by word. 
 * For example, given s = "the sky is blue", return "blue is sky the". 
 * NOTES: 
 * 1. A sequence of non-space characters constitutes a word. 
 * 2. Remove all leading and trailing spaces. 
 * 3. Reduce multiple spaces between words into a single space.
 * 
 */
 
public class ReverseWordsInAString {
	// Reverse characters in an array from given index 'start' till index 'end'
    static void reverseCharacters(char[] arr, int start, int end){
		while(start < end){
			char temp = arr[start];
			arr[start] = arr[end];
			arr[end] = temp;
			start++;
			end--;
		}
	}
	
	/**
	 * Sample outputs from reverseWords function:
	 * s = "   no pain is equal to no gain lorem ipsum ftw!   ", returns "ftw! ipsum lorem gain no to equal is pain no"
	 * s = "  here is some     special     sauce   .  ", returns ". sauce special some is here"
	 * s = ";    ", returns ";"
	 * s = "    i am here", returns "here am i"
	 * s = "absolutely normal", returns "normal absolutely"
	 * s = "      ", returns ""
	 * s = " ", returns ""
	 */
	public String reverseWords(String s){
		if(s == null || s.equals("")) return s; // Null or empty string
		
		char[] allChars = s.toCharArray();
		
		// STEP 1: Reverse the characters of each word in the string
		int leftBound = 0;
		int rightBound = 0;
		boolean seeingWord = false;
		boolean nothingButSpaces = true;
		for(int i = 0; i < allChars.length; i++){
			// We saw a new word
			if(allChars[i] != ' ' && !seeingWord){
				leftBound = i;
				seeingWord = true;
				nothingButSpaces = false;
			}
			// We reached the first space after the current word
			else if((allChars[i] == ' ') && seeingWord){
				rightBound = i - 1;
				reverseCharacters(allChars, leftBound, rightBound);
				seeingWord = false;
			}
			// We reached the end of the string and we were seeing a new word
			else if(i == allChars.length - 1 && seeingWord){
				rightBound = i;
				reverseCharacters(allChars, leftBound, rightBound);
			}
		}
		
		// The string is nothing but spaces, so return an empty string
		if(nothingButSpaces){ 
			return "";
		}
		
		// STEP 2: Reverse the characters in the string and trim extra spaces
		StringBuilder result = new StringBuilder();
		int pseudoStart = 0;
		int pseudoEnd = allChars.length - 1;
		
		// Trim leading and trailing spaces
		while(allChars[pseudoStart] == ' ' && pseudoStart < pseudoEnd) pseudoStart++;
		while(allChars[pseudoEnd] == ' ' && pseudoEnd > pseudoStart) pseudoEnd--;
		
		// Read the characters in reverse taking care to convert multiple spaces
		// between words to a single space
		boolean seenSpace = false;
		for(int j = pseudoEnd; j >= pseudoStart; j--){
			// We saw the first space after a word
			if(allChars[j] == ' ' && !seenSpace){
				result.append(allChars[j]);
				seenSpace = true;
			}
			// Blindly copy non-space characters and ensure 'seenSpace' flag is cleared
			else if(allChars[j] != ' '){
				result.append(allChars[j]);
				seenSpace = false;
			}
		}
		
		return result.toString();   
	}
}