Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a string s of words delimited by spaces, reverse the order of words.
Constraints
n ≤ 100,000 where n is the length of s
Example 1
Input
sentence = “hello there my friend”
Output
“friend my there hello”
Reverse and Reverse Algorithm
First, we can reverse the entire string, then, we can reverse the words. However, since strings are immutable, therefore, we convert the string to character array, then finally join them as a string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution: def reverseWords(self, sentence): def rev(s, i, j): while i < j: s[i], s[j] = s[j], s[i] i += 1 j -= 1 s = list(sentence[::-1]) prev = 0 for i, c in enumerate(s): if c == ' ': rev(s, prev, i - 1) prev = i + 1 rev(s, prev, len(s) - 1) return ''.join(s) |
class Solution:
def reverseWords(self, sentence):
def rev(s, i, j):
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
s = list(sentence[::-1])
prev = 0
for i, c in enumerate(s):
if c == ' ':
rev(s, prev, i - 1)
prev = i + 1
rev(s, prev, len(s) - 1)
return ''.join(s)We have previous index and when we meet a space, we reverse the part [prev, cur]. Don’t forget the last word.
Python One-Liner to Reverse Words
Using Python, we can do this using one liner. First split by words, reverse them, and then join by space.
1 2 3 | class Solution: def reverseWords(self, sentence): return ' '.join(sentence.split(' ')[::-1]) |
class Solution:
def reverseWords(self, sentence):
return ' '.join(sentence.split(' ')[::-1])or using the reversed function which is equivalent to [::-1].
1 2 3 | class Solution: def reverseWords(self, sentence): return " ".join(reversed(sentence.split())) |
class Solution:
def reverseWords(self, sentence):
return " ".join(reversed(sentence.split()))See also: How to Reverse String in C++?
Reverse words in C++
C++ does not have a good inbuilt string split, but we can parse the tokens (delimiter by spaces) using the istringstream.
1 2 3 4 5 6 7 8 9 10 11 12 13 | string reverseWords(string sentence) { string ans = ""; istringstream ss(sentence); vector<string> words; string word; while (ss >> word) { words.push_back(word); } for (const auto &r: words) { ans = r + " " + ans; } return ans.substr(0, ans.size() - 1); } |
string reverseWords(string sentence) {
string ans = "";
istringstream ss(sentence);
vector<string> words;
string word;
while (ss >> word) {
words.push_back(word);
}
for (const auto &r: words) {
ans = r + " " + ans;
}
return ans.substr(0, ans.size() - 1);
}–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Dynamic Programming Algorithm to Count the Exact Sum of Subsets
Next Post: Breadth First Search Algorithm to Compute the Sum of a Binary Tree
