Posts Reverse Words in a String
Post
Cancel

Reverse Words in a String

PROBLEM DESCRIPTION

Given an input string s, reverse the order of the words. A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space. Return a string of the words in reverse order concatenated by a single space. Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

leetcode

SOLUTION (WITHOUT IN-BUILT METHODS)

We can easily use split function and iterate through the String array from right to left to get the result. To achieve the same using just a simple loop, we can do it in the following way:

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
class Solution {
    
    public String reverseWords(String s) {

        int n = s.length();
        
        int i = n-1;
        int j = n-1;

        //skip the trailing white space
        //(we could have simply used trim() method also)
        while(s.charAt(i) == ' '){
            i--; j--;
        }

        //ans string
        StringBuilder sb = new StringBuilder();

        //while there are character to check
        while(i>=0){
            
            //if the char at i is not empty, go to left
            while(i>=0 && s.charAt(i) != ' '){
                i--;
            }

            //the char at i must be empty, so we have found a word from [i+1,j]
            //append that to the ans string
            for(int x=i+1; x<=j; x++){
                sb.append(s.charAt(x));
            }

            //set i,j to the end of next word from right
            //there can be empty space, so skip them
            j=i;
            while(i>=0 && s.charAt(i) == ' '){
                j--; i--;
            }

            //add a space since this is not the last word
            if(i>=0) sb.append(" ");

        }

        return sb.toString();

    }

}
This post is licensed under CC BY 4.0 by the author.