Reverse Words In A String Problem


Description

LeetCode Problem 151.

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.

Example 1:

1
2
Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

1
2
3
Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

1
2
3
Input: s = "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.

Example 4:

1
2
Input: s = "  Bob    Loves  Alice   "
Output: "Alice Loves Bob"

Example 5:

1
2
Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"

Constraints:

  • 1 <= s.length <= 10^4
  • s contains English letters (upper-case and lower-case), digits, and spaces ‘ ‘.
  • There is at least one word in s.


Sample C++ 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
class Solution {
public:
    void reverseword(string &s, int i, int j){
        while(i<j){
          char t=s[i];
          s[i++]=s[j];
          s[j--]=t;
        } 
    }
    
    void reverseWords(string &s) {
        int i=0, j=0;
        int l=0;
        int len=s.length();
        int wordcount=0;
        
        while(true){
            while(i<len && s[i] == ' ') i++;  
            if(i==len) break;
            if(wordcount) s[j++]=' ';
            l=j;
            while(i<len && s[i] != ' ') {s[j]=s[i]; j++; i++;} 
            reverseword(s,l,j-1);              
            wordcount++;
            
        }
        
        s.resize(j);                          
        reverseword(s,0,j-1);                
    }
};




Related Posts

Reverse Words In A String Problem

LeetCode 151. Given an input string s, reverse the order...

Compare Version Numbers Problem

LeetCode 165. Given two version numbers,version1 and version2, compare them....

Valid Palindrome Problem

LeetCode 125. A phrase is a palindrome if, after converting...

Remove Duplicates from Sorted List II Problem

LeetCode 82. Given the head of a sorted linked list,...

Remove Duplicates from Sorted Array II Problem

LeetCode 80. Given an integer array nums sorted in non-decreasing...

Partition List Problem

LeetCode 86. Given the head of a linked list and...