Reverse Words in a String 3

Problem

Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Examples

Example 1:

Input:
s = "Let's take LeetCode contest"
Output:
 "s'teL ekat edoCteeL tsetnoc"

Example 2:

Input:
s = "God Ding"
Output:
 "doG gniD"

Solution

Method 1 - Form the words in reverse order and append

Code

Java
public String reverseWords(String s) {
	final StringBuilder result = new StringBuilder();
	final StringBuilder word = new StringBuilder();
	for (int i = 0; i < s.length(); i++) {
		if (s.charAt(i) != ' ') {
			word.insert(0, s.charAt(i)); // no need to reverse
		} else {
			result.append(word);
			result.append(" ");
			word.setLength(0);
		}
	}
	// last word
	result.append(word);
	return result.toString();
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 2 - Use string reverse

public class Solution {

	public String reverseWords(String s) {
		char[] a = s.toCharArray();

		for (int i = 0; i < a.length; i++) {
			if (a[i] != ' ') {
				int j = i;

				while (j + 1 < a.length && a[j + 1] != ' ') {
					j++; // move j to the end of the word 
				}

				reverse(a, i, j);
				i = j;
			}
		}

		return new String(ca);
	}

	private void reverse(char[] a, int i, int j) {
		for (; i < j; i++, j--) {
			char tmp = ca[i];
			a[i] = ca[j];
			a[j] = tmp;
		}
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)