Problem

Given a string and a set of delimiters, reverse the words in the string while maintaining the relative order of the delimiters. For example, given “hello/world:here”, return “here/world:hello”

Follow-up

Does your solution work for the following cases: "hello/world:here/", "hello//world:here"

Examples

Example 1:

1
2

Input: s = hello/world:here
Output: here/world:hello

Solution

Method 1 - Using stack to store words and queue for delimiters

Code

 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

class Solution {

	public String reverseWords(String s) {
		Stack<String> stack = new Stack<>();
		Queue<String> queue = new LinkedList<>();

		StringBuilder word = new StringBuilder();
		int i = 0;

		while (i < s.length()) {
			char c = s.charAt(i);

			if (Character.isLetterOrDigit(c)) {
				word.append(c);
				i++;
			} else {
				if (word.length() > 0) {
					stack.push(word.toString());
				}

				word = new StringBuilder(); // clear word for next word
				StringBuilder delim = new StringBuilder();
				delim.append(c);
				i++;
				// tracking continuous delimiter to add to queue
				while (i < s.length() && !Character.isLetterOrDigit(s.charAt(i))) {
					delim.append(c);
					i++;
				}

				queue.add(delim.toString());
			}
		}

		// if string ends with words
		if (word.length() != 0) {
			stack.push(word.toString());
		}

		boolean isWordFirst = Character.isLetterOrDigit(s.charAt(0));
		StringBuilder sb = new StringBuilder();

		// if word is not first, add 1 entry from queue
		if (!isWordFirst) {
			if (!queue.isEmpty()) {
				sb.append(queue.remove());
			}
		}
		// now put 1 element from either till not empty
		while (!stack.isEmpty() || !queue.isEmpty()) {
			if (!stack.isEmpty()) {
				sb.append(stack.pop());
			}

			if (!queue.isEmpty()) {
				sb.append(queue.remove());
			}
		}

		return sb.toString();
	}
}

Complexity

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