151. Reverse Words in a String

Description

Given an input string, reverse the string word by word.

Note:

• A word is defined as a sequence of non-space characters.

• Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.

• You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: "the sky is blue"

Output: "blue is sky the"

Example 2

Input: " hello world! "

Output: "world! hello"

Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3

Input: "a good example"

Output: "example good a"

Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public String reverseWords(String s) {
        int i = s.length()-1;
        StringBuilder result = new StringBuilder();
        while(i >= 0) {
            while(i >= 0 && s.charAt(i) == ' ') {
                i--;
            }
            String tmp = "";
            while(i >= 0 && s.charAt(i) != ' ') {
                tmp = s.charAt(i) + tmp;
                i--;
            }
            if(tmp.length() > 0) {
                result.append(" ").append(tmp);
            }
        }
        if(result.length() == 0) {
            return result.toString();
        }
        return result.substring(1);
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    public String reverseWords(String s) {
        StringBuilder result = new StringBuilder();
        String[] words = s.split(" ");
        
        for(int i = words.length-1; i >= 0; i--) {
            if(words[i].isEmpty()) continue;
            result.append(words[i]).append(" ");
        }
        
        return result.toString().trim();
    }
}

Follow up