0500 - 0599
0557 - Reverse Words in a String III (Easy)
Problem Link
https://leetcode.com/problems/reverse-words-in-a-string-iii/
Problem Statement
Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"Example 2:
Input: s = "God Ding"
Output: "doG gniD"Constraints:
1 <= s.length <= 5 * 10^4scontains printable ASCII characters.sdoes not contain any leading or trailing spaces.- There is at least one word in
s. - All the words in
sare separated by a single space.
Approach 1: Split and Reverse
class Solution {
public:
// custom split template
vector<string> split(string str, char delim) {
string line;
vector<string> res;
stringstream ss(str);
while (getline(ss, line, delim)) res.push_back(line);
return res;
}
string reverseWords(string s) {
// split by ' '
vector<string> v = split(s, ' ');
// reverse each string
for(auto &x : v) reverse(x.begin(), x.end());
// construct the answer
string ans;
for(int i = 0; i < v.size(); i++) {
ans += v[i];
// add space after each string except the last one
if(i != v.size() - 1) ans += " ";
}
return ans;
}
};Approach 2: Two Pointers
class Solution {
public:
string reverseWords(string s) {
int l = 0, r = 0, n = s.size();
for (int i = 0; i < n; i++) {
// looking for the space index
if (s[i] == ' ' || i == n - 1) {
// r is the index before the space
// if s[i] is space, then we want to reverse s[l : i - 1]
// if s[i] is the last character, then we want to reverse s[l : i]
r = i == n - 1 ? i : i - 1;
// swap the character
// e.g. s = `Let's` where l is 0 and r is 4
// Let's -> set'L -> s'teL
while (l < r) swap(s[l++], s[r--]);
// update left pointer which is i + 1
// i.e. the first index of the next word if applicable
l = i + 1;
}
}
return s;
}
};