ReverseWordsInAString [source code]
public class ReverseWordsInAString {
static
/******************************************************************************/
public class Solution {
public String reverseWords(String s) {
String[] tokens = s.split ("\\s+");
StringBuilder sb = new StringBuilder ();
for (int i = tokens.length - 1; i >= 0; i--) {
sb.append (tokens[i]);
if (i > 0)
sb.append (" ");
}
return sb.toString ().trim ();
}
}
/******************************************************************************/
public static void main(String[] args) {
ReverseWordsInAString.Solution tester = new ReverseWordsInAString.Solution();
String[] inputs = {
" 1", "1",
"the sky is blue", "blue is sky the",
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
String s = inputs[2 * i], ans = inputs[2 * i + 1], output = tester.reverseWords (s);
System.out.printf ("%s -> %s, expected: %s\n",
s, Printer.wrap (output, output.equals (ans) ? 92 : 91), ans
);
}
}
}
看起来很蠢的一个题目, 怎么AC rate这么低?
另外, 再次回顾split的奇怪行为:
java> " a ".split ("")
java.lang.String[] res0 = [" ", "a", " "]
java> " a ".split (" ")
java.lang.String[] res1 = ["", "a"]
java> "a ".split (" ")
java.lang.String[] res2 = ["a"]
java> " a".split (" ")
java.lang.String[] res3 = ["", "a"]
java> " ".split (" ")
java.lang.String[] res4 = []
java> "".split (" ")
java.lang.String[] res5 = [""]
根据上面的这个, 可以看到, 最后我们会得到类似"a", ""这样的tokens, 注意对这个的处理就行了; 最后直接就AC了, 速度是10ms (43%);
没有editorial;
https://leetcode.com/problems/reverse-words-in-a-string/discuss/47740/In-place-simple-solution
First, reverse the whole string, then reverse each word.
void reverseWords(string &s) {
reverse(s.begin(), s.end());
int storeIndex = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] != ' ') {
if (storeIndex != 0) s[storeIndex++] = ' ';
int j = i;
while (j < s.size() && s[j] != ' ') { s[storeIndex++] = s[j++]; }
reverse(s.begin() + storeIndex - (j - i), s.begin() + storeIndex);
i = j;
}
}
s.erase(s.begin() + storeIndex, s.end());
}
大概画了一下:
好像也没有什么特别的, 就是一个分段算法配合reverse的使用;
这个算法的一个核心思路是, 比如, 假如我们不reverse, 直接read从左到右, write从右到左, 行不行? 这个是不行的, 假如"abc"这样的, 只有一个词, 那么最后两个指针就要重叠, 处理起来就很麻烦; 他这里先reverse之后, 快慢指针在一个方向上, 这个我们知道, 快慢指针是不用担心重叠和交界问题的;
public class Solution {
public String reverseWords(String s) {
if (s == null) return null;
char[] a = s.toCharArray();
int n = a.length;
// step 1. reverse the whole string
reverse(a, 0, n - 1);
// step 2. reverse each word
reverseWords(a, n);
// step 3. clean up spaces
return cleanSpaces(a, n);
}
void reverseWords(char[] a, int n) {
int i = 0, j = 0;
while (i < n) {
while (i < j || i < n && a[i] == ' ') i++; // skip spaces
while (j < i || j < n && a[j] != ' ') j++; // skip non spaces
reverse(a, i, j - 1); // reverse the word
}
}
// trim leading, trailing and multiple spaces
String cleanSpaces(char[] a, int n) {
int i = 0, j = 0;
while (j < n) {
while (j < n && a[j] == ' ') j++; // skip spaces
while (j < n && a[j] != ' ') a[i++] = a[j++]; // keep non spaces
while (j < n && a[j] == ' ') j++; // skip spaces
if (j < n) a[i++] = ' '; // keep only one space
}
return new String(a).substring(0, i);
}
// reverse a[] from a[i] to a[j]
private void reverse(char[] a, int i, int j) {
while (i < j) {
char t = a[i];
a[i++] = a[j];
a[j--] = t;
}
}
}
反正这个题目考察的就是造轮子了; 他这里这个reverseWords (char[], int)实现的还是挺有意思的;
The code could be slightly faster by running the space cleaning function first, since less iterations would be needed in the reverse function loops.
This is supposed to be the highest accepted solution.
Resolve the problem from the bottom.
I don’t understand why the answer with Java library got sooooo many upvotes.
确实是这个样子, 跑过去面试一堆API调用的, 肯定是不行的; 如果直接用API, 这个题目就真的easy水平;
另外, 仅仅是不使用API, 也不代表就真的能够理解这个题目, 这个题目还有一个很简单的方法, 从左到右扫一遍, 记录所有的end of words index, 然后再专门反过来扫一遍往一个结果里面丢就行了; 这个其实也很trivial; 所以这个题目如果真的想要锻炼, 需要写InPlace的思路;
“\s” is a regex class for any kind of whitespace (space, tab, newline, etc). Since Java uses “\” as an escape character in strings (e.g. for newlines: “
”), we need to escape the escape character ;-) So it becomes “\\s”. The “+” means one or more of them.
The idea is to ignore the extra spaces, reverse words one by one and reverse the whole string in the end.
I think for the interview it is good to show that substr or istringstream can be used too.
The idea is taken from here
class Solution {
public:
// function to reverse any part of string from i to j (just one word or entire string)
void reverseword(string &s, int i, int j){
while(i<j){
char t=s[i];
s[i++]=s[j];
s[j--]=t;
}
}
void reverseWords(string &s) {
int i=0, j=0;
int l=0;
int len=s.length();
int wordcount=0;
while(true){
while(i<len && s[i] == ' ') i++; // skip spaces in front of the word
if(i==len) break;
if(wordcount) s[j++]=' ';
l=j;
while(i<len && s[i] != ' ') {s[j]=s[i]; j++; i++;}
reverseword(s,l,j-1); // reverse word in place
wordcount++;
}
s.resize(j); // resize result string
reverseword(s,0,j-1); // reverse whole string
}
};
上面这个是14年的, 16年的时候好像就不用自己写reverse了:
class Solution {
public:
void reverseWords(string &s) {
int sz = s.size();
int i = 0, j = 0;
while (i < sz)
{
while (i < sz && s[i] == ' ') i++; //i is the start of the word
if (i < sz && j > 0)
s[j++] = ' ';
int start = j;
while (i < sz && s[i] != ' ')
s[j++] = s[i++];
reverse(s.begin()+start, s.begin()+j);
}
s.resize(j);
reverse(s.begin(), s.end());
}
};
submission最优解: 3(88):
public class Solution {
public String reverseWords(String s) {
if(s == null || s.length() == 0) return "";
StringBuilder sb = new StringBuilder();
String[] str = s.split("\\ ");
for(int i = str.length - 1; i >= 0; i--){
String ss = str[i];
if(!ss.isEmpty()){
sb.append(ss).append(" ");
}
}
if(sb.length() != 0)
sb.setLength(sb.length() - 1);
return sb.toString();
}
}
跟我的做法是一样的, 为什么比我的快这么多?
Problem Description
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.
click to show clarification.
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.
Difficulty:Medium
Total Accepted:187.4K
Total Submissions:1.2M
Contributor:LeetCode
Companies
microsoftbloombergapplesnapchatyelp
Related Topics
string
Similar Questions
Reverse Words in a String II