Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/151.html
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:
Input: s = "the sky is blue" Output: "blue is sky the"
Example 2:
Input: s = " hello world " Output: "world hello" Explanation: Your reversed string should not contain leading or trailing spaces.
Example 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.
Constraints:
1 <= s.length <= 104
s
contains English letters (upper-case and lower-case), digits, and spaces' '
.- There is at least one word in
s
.
Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1)
extra space?
Algorithm
First flip the entire string once, and then flip each word separately (or flip each word separately, and then flip the entire string once).
If we use Java’s String split
function to do it, it is very simple, there are not so many moths, simple and clear.
- we first call the original string to
trim()
to remove redundant spaces, - and then call
split()
to separate , The delimiter is set to"\\s+"
, this is actually a regular expression,\\s
means space character,+
means there can be one or more space characters, - then we can separate the words into one character in the string array, then we start from the end, take out the words one by one and add them to the result
res
, and add space characters between the words.Note
that we leave the first word, and then add it when returning.
Code
-
public class Reverse_Words_in_a_String { public class Solution { public String reverseWords(String s) { if (s == null || s.length() == 0) { return s; } String res = ""; String[] words = s.trim().split("\\s+"); for (int i = words.length - 1; i > 0; --i) { res += words[i] + " "; } return res + words[0]; } } public class Solution_sb { public String reverseWords(String s) { String res = ""; String[] words = s.trim().split("\\s+"); for (int i = words.length - 1; i > 0; --i) { res += words[i] + " "; } return res + words[0]; } } // basically, 1st scan to reverse whole string including space, // 2nd scan to reverse each word when encountering a space public class Solution_2Scan { public String reverseWords(String s) { if (s == null || s.length() == 0) { return s; } int storeIndex = 0, n = s.length(); StringBuilder sb = new StringBuilder(s).reverse(); for (int i = 0; i < n; ++i) { if (sb.charAt(i) != ' ') { if (storeIndex != 0) sb.setCharAt(storeIndex++, ' '); int j = i; while (j < n && sb.charAt(j) != ' ') sb.setCharAt(storeIndex++, sb.charAt(j++)); String t = new StringBuilder(sb.substring(storeIndex - (j - i), storeIndex)).reverse().toString(); sb.replace(storeIndex - (j - i), storeIndex, t); i = j; } // else, skip space } sb.setLength(storeIndex); return sb.toString(); } } } ############ class Solution { public String reverseWords(String s) { List<String> words = Arrays.asList(s.trim().split("\\s+")); Collections.reverse(words); return String.join(" ", words); } }
-
// OJ: https://leetcode.com/problems/reverse-words-in-a-string/ // Time: O(S) // Space: O(1) class Solution { public: void reverseWords(string &s) { int i = 0, j = 0; while (j < s.size()) { while (j < s.size() && s[j] == ' ') ++j; if (i != 0 && j != s.size()) s[i++] = ' '; while (j < s.size() && s[j] != ' ') s[i++] = s[j++]; } s.erase(i); i = j = 0; while (i < s.size()) { j = i; while (j < s.size() && s[j] != ' ') ++j; reverse(s.begin() + i, s.begin() + j); i = j + 1; } reverse(s.begin(), s.end()); } };
-
class Solution: def reverseWords(self, s: str) -> str: words = s.strip().split() return ' '.join(words[::-1]) ############ class Solution: # O(1) space complexity def reverseWords(self, s: str) -> str: # Remove leading and trailing spaces s = s.strip() # Reverse the entire string s = self.reverseString(s, 0, len(s) - 1) # Reverse each word in the string start = 0 end = 0 while end < len(s): if s[end] == ' ': s = self.reverseString(s, start, end - 1) start = end + 1 end += 1 # Reverse the last word s = self.reverseString(s, start, end - 1) return s def reverseString(self, s: str, start: int, end: int) -> str: # Convert the string to a list of characters chars = list(s) # Reverse the substring while start < end: chars[start], chars[end] = chars[end], chars[start] start += 1 end -= 1 # Convert the list of characters back to a string return ''.join(chars) ############ class Solution(object): def reverseWords(self, s): """ :type s: str :rtype: str """ return " ".join(s.split()[::-1])
-
function reverseWords(s: string): string { return s.trim().split(/\s+/).reverse().join(' '); }
-
public class Solution { public string ReverseWords(string s) { return string.Join(" ", s.Trim().Split(" ").Where(word => !string.IsNullOrEmpty(word) && !string.IsNullOrEmpty(word.Trim())).Reverse()); } }
-
impl Solution { pub fn reverse_words(s: String) -> String { s.split_whitespace().rev().collect::<Vec<&str>>().join(" ") } }
-
func reverseWords(s string) string { words := strings.Split(s, " ") var ans []string for i := len(words) - 1; i >= 0; i-- { if words[i] != "" { ans = append(ans, words[i]) } } return strings.Join(ans, " ") }