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.
Solution 1: 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(); }
Solution 2: one-pass.
We can do better in one-pass. While iterating the string in reverse order, we keep track of a word’s begin and end position. When we are at the beginning of a word, we append it.
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(); }
重构了以下以上代码:
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(); }
Solution 3:
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; } }
相关推荐
Reverse words in a string-leetcode
421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...
557. 反转字符串中的单词 IIIpublic String reverseWords(String s) {StringBuilder sb = new S
第 338 章概括 [(雅虎)4。 两个排序数组的中位数](Leetcode 问题/数组和字符串/4.median_of_two_sorted_array.md) [(雅虎)13。...String/151.reverse_words_in_a_string.md) [167. Two Sum 2 - In
leetcode 2 sum c Leetcode 练习记录 这个专案主要存放我练习Leetcode有针对难度分类的集合题库(Collection Question) 准备方式 分析tag的热门标签,熟悉各个标签解题的思路(解决该标签全部的easy和medium为主),再...
reverseWords titleToNumber toLowerCase defangIPaddr replaceSpace removeOuterParentheses 复杂题目值得参考 sortString 使用字典排序 sort((a, b) => a.charCodeAt() - b.charCodeAt()) 有参考价值 Maths isPal
goMy solution to LeetCode problems using GolangProblems 题库Array 数组NoTitle题名DifficultyStatus11Container With Most Water盛最多水的容器MediumSolved26Remove Duplicates from Sorted Array删除有序数组...
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
2 Reverse Words in a String II 19 3 Evaluate Reverse Polish Notation 21 4 Isomorphic Strings 25 5 Word Ladder 27 6 Word Ladder II 29 7 Median of Two Sorted Arrays 33 8 Kth Largest Element in an Array ...
题目描述 151. 翻转字符串里的单词 解法一:(Python) class Solution: def reverseWords(self, s: str) -> str: return " ".join(reversed(s.split())) 解法二:双端队列(C++) ... string reverseWords(strin
reverseWords 翻转字符串里的单词 simplifyPath 简化路径 restoreIPAddresses 复原IP地址 threeSum 三数之和 search 搜索旋转排序数组 1. 3. 9. 75. 209. 219. 167. 268. 344. 349. 454. 447. 695. 674. string 字符...
Reverse Nodes in k-Group Copy List with Random Pointer Linked List Cycle Linked List Cycle II Reorder List LRU Cache Palindrome Linked List 字符串 Valid Palindrome Implement strStr() String to Integer...