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:

1
2
3
4

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

Example 2:

1
2
3
4

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

Solution

Method 1 - Form the words in reverse order and append

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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)