- Given an input string, reverse the string word by word.
- For example,
- Given s = "the sky is blue",
- return "blue is sky the".
- Update (2015-02-12):
- For C programmers: Try to solve it in-place in O(1) space.
- Clarification:
- What constitutes a word?
- A sequence of non-space characters constitutes a word.
- Could the input string contain leading or trailing spaces?
- Yes. However, your reversed string should not contain leading or trailing spaces.
- How about multiple spaces between two words?
- Reduce them to a single space in the reversed string.
把一个字符串中的单词逆序, 单词字符顺序不变
解法 1: New array, 新建一个数组, 把字符串以空格拆分成单词存到数组, 在把单词逆序拷贝进新数组
解法 2: One place, 不能新建数组, 在原数组的基础上换位把字符串的所以字符逆序, 然后在把每个单词的字符逆序
- Java: New array, two pass
- public String reverseWords(String s) {
- String[] words = s.trim().split("\\s+");
- if(words.length == 0) {
- return "";
- }
- StringBuilder sb = new StringBuilder(words[words.length-1]);
- for(int i=words.length-2; i >=0; i--) {
- sb.append(" "+words[i]);
- }
- return sb.toString();
- }
- Java: New array, one pass
- public String reverseWords(String s) {
- StringBuilder sb = new StringBuilder();
- int end = s.length();
- int i = end-1;
- while(i>=0) {
- if(s.charAt(i) == ) {
- if(i < end-1) {
- sb.append(s.substring(i+1, end)).append(" ");
- }
- end = i;
- }
- i--;
- }
- sb.append(s.substring(i+1, end));
- return sb.toString().trim();
- }
- Java: New array, one pass
- public String reverseWords(String s) {
- StringBuilder sb = new StringBuilder();
- int last = s.length();
- for(int i=s.length()-1; i>=-1; i--) {
- if(i==-1 || s.charAt(i)== ) {
- String word = s.substring(i+1, last);
- if(!word.isEmpty()) {
- if(sb.length() != 0) sb.append( );
- sb.append(word);
- }
- last = i;
- }
- }
- return sb.toString();
- }
- Java:One place
- public String reverseWords(String s) {
- if(s == null || s.isEmpty()) return s;
- char[] data = s.toChartArray();
- int n = data.length;
- reverse(data, 0, n-1);
- int last = -1;
- for(int i=0; i<=n; i++) {
- if(i == n || data[i] == ) {
- if(i-last>1) reverse(data, last+1, i-1);
- last = i;
- }
- }
- return new String(data);
- }
- private void reverse(char[] data, int start, int end) {
- while(start < end) {
- char tmp = data[start];
- data[start++] = data[end];
- data[end--] = tmp;
- }
- }
- Python: New array
- class Solution:
- # @param s, a string
- # @return a string
- def reverseWords(self, s):
- return .join(reversed(s.split()))
- C++:
- class Solution {
- public:
- void reverseWords(string &s) {
- int storeIndex = 0, n = s.size();
- reverse(s.begin(), s.end());
- for (int i = 0; i < n; ++i) {
- if (s[i] != ) {
- if (storeIndex != 0) s[storeIndex++] = ;
- int j = i;
- while (j < n && s[j] != ) s[storeIndex++] = s[j++];
- reverse(s.begin() + storeIndex - (j - i), s.begin() + storeIndex);
- i = j;
- }
- }
- s.resize(storeIndex);
- }
- };
类似题目:
[LeetCode] 186. Reverse Words in a String II 翻转字符串中的单词 II
[LeetCode] 557. Reverse Words in a String III 翻转字符串中的单词 III
来源: http://www.bubuko.com/infodetail-2522039.html