Reverse Words in a String - 未名空间MITBBS历史存档

Reverse Words in a String# JobHunting - 待字闺中

h*22014-03-06 08:03

1 楼

Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
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 sp
aces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.
基本思路就是先整体reverse string (character per character), 之后对于每个word
reverse (character per character)，但这题有个要求就是要把多余的spaces去掉，
这个是在per word reverse 里面做呢还是最后再扫一遍呢？
问下大家~~

e*i2014-03-06 08:03

2 楼

public class Solution {
public String reverseWords(String s) {
s=s.trim();
StringBuilder sb=new StringBuilder();
for(String t:s.split(" +"))
sb.insert(0,t+" ");
return sb.toString().trim();
}
}

sp

【在 h*********2 的大作中提到】

: Given an input string, reverse the string word by word.
: For example,
: Given s = "the sky is blue",
: return "blue is sky the".
: 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 sp
: aces.

h*62014-03-06 08:03

3 楼

上个不用api的
public String reverseWords(String s) {
if (s == null || s.length() == 0) {
return s;
}
int len = s.length();
Stack stack = new Stack();
int start = 0;
int i = 0;
while (i < len) {
if (s.charAt(i) == ' ') {
if (start != i) {
stack.push(s.substring(start, i));
}
while (i < len && s.charAt(i) == ' ') {
i++;
}
start = i;
} else {
i++;
}
}
if (start < len) {
stack.push(s.substring(start, len));
}
if (stack.isEmpty()) {
return "";
} else {
StringBuilder sb = new StringBuilder();
sb.append(stack.pop());
while (!stack.isEmpty()) {
sb.append(" ");
sb.append(stack.pop());
}
return sb.toString();
}
}

g*s2014-03-06 08:03

4 楼

Just saw this questiong #151 one LeetCode :)
I used a stack and string.split() method.
private static String reverseWords(String s) {
if(s.length() == 0) return s;
String[] split = s.split(" ");

int Len = split.length;
if(Len == 0) return "";
Stack stc = new Stack();
for(int i=0; iif(!split[i].equals("")
stc.push(split[i]);
}
String retStr = stc.pop();
while(!stc.isEmpty()){
retStr += " " +stc.pop();
}
return retStr;
}

f*w2014-03-06 08:03

5 楼

都是java的啊
我来个python的- -
class Solution:
def reverseWords(self, s):
words = s.split()
words.reverse()
return ' '.join(words)

f*w2014-03-06 08:03

6 楼

C++的
class Solution {
public:
void reverseWords(string &s) {
stack np;
size_t lastPos = s.find_first_not_of(" ", 0);
size_t pos = s.find_first_of(" ", lastPos);
while (string::npos != pos || string::npos != lastPos) {
if (lastPos != pos) {
string str = s.substr(lastPos, pos - lastPos);
np.push(str);
}
lastPos = s.find_first_not_of(" ", pos);
pos = s.find_first_of(" ", lastPos);
}
s = "";
while ((int)np.size() > 1) {
string str = np.top();
np.pop();
s += str + " ";
}
if ((int)np.size() > 0) s += np.top();
}
};

f*s2014-03-06 08:03

7 楼

class Solution {
public:
void reverseWords(string &s) {
stack ss;
istringstream is(s);
string word;

while(is>>word){
ss.emplace(word);
}

s = "";
while(!ss.empty()){
s += ss.top()+" ";
ss.pop();
}
if(s.length() > 0)
s.pop_back();
}
};

c*62014-03-06 08:03

8 楼

static String reverseWords(String s)
{
if(s.length() == 0) return s;
s += " ";
StringBuilder temp = new StringBuilder();
Stack stack = new Stack();
for(int i = 0; i < s.length(); i++)
{
char c = s.charAt(i);
if(c == ' ')
{
if(temp.length() > 0) stack.push(temp.toString());
temp = new StringBuilder();
}
else temp.append(c);
}
if(stack.isEmpty()) return "";
StringBuilder result = new StringBuilder();
while(!stack.isEmpty())
{
result.append(stack.pop());
if(!stack.isEmpty()) result.append(" ");
}
return result.toString();
}

b*s2014-03-06 08:03

9 楼

def solve(s):
return ' '.join(w for w in reversed(s.split()))

S*I2014-03-06 08:03

10 楼

乱棍打出去。:)

【在 b*********s 的大作中提到】

: def solve(s):
: return ' '.join(w for w in reversed(s.split()))

g*42014-03-06 08:03

11 楼

遇到不是space就把char存在临时的string里，遇到space就终止，把临时的string给存
了，什么额外的条件都无所谓
以下是C++
感觉OJ有问题，换了substr也出错
class Solution {
public:
void reverseWords(string &s) {
string ret = "";
for (int i = 0; i < s.length(); i++) {
string word = "";
while (!isspace(s[i])) {
word += s[i];
i++;
}
if (word.length() != 0) {
if (ret.length() == 0) {
ret = word;
}else {
ret = word + " " + ret;
}
}
}
s = ret;
}
};

h*22014-03-06 08:03

12 楼

Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
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 sp
aces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.
基本思路就是先整体reverse string (character per character), 之后对于每个word
reverse (character per character)，但这题有个要求就是要把多余的spaces去掉，
这个是在per word reverse 里面做呢还是最后再扫一遍呢？
问下大家~~

e*i2014-03-06 08:03

13 楼

public class Solution {
public String reverseWords(String s) {
s=s.trim();
StringBuilder sb=new StringBuilder();
for(String t:s.split(" +"))
sb.insert(0,t+" ");
return sb.toString().trim();
}
}

sp

【在 h*********2 的大作中提到】

: Given an input string, reverse the string word by word.
: For example,
: Given s = "the sky is blue",
: return "blue is sky the".
: 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 sp
: aces.

h*62014-03-06 08:03

14 楼

上个不用api的
public String reverseWords(String s) {
if (s == null || s.length() == 0) {
return s;
}
int len = s.length();
Stack stack = new Stack();
int start = 0;
int i = 0;
while (i < len) {
if (s.charAt(i) == ' ') {
if (start != i) {
stack.push(s.substring(start, i));
}
while (i < len && s.charAt(i) == ' ') {
i++;
}
start = i;
} else {
i++;
}
}
if (start < len) {
stack.push(s.substring(start, len));
}
if (stack.isEmpty()) {
return "";
} else {
StringBuilder sb = new StringBuilder();
sb.append(stack.pop());
while (!stack.isEmpty()) {
sb.append(" ");
sb.append(stack.pop());
}
return sb.toString();
}
}

g*s2014-03-06 08:03

15 楼

Just saw this questiong #151 one LeetCode :)
I used a stack and string.split() method.
private static String reverseWords(String s) {
if(s.length() == 0) return s;
String[] split = s.split(" ");

int Len = split.length;
if(Len == 0) return "";
Stack stc = new Stack();
for(int i=0; iif(!split[i].equals("")
stc.push(split[i]);
}
String retStr = stc.pop();
while(!stc.isEmpty()){
retStr += " " +stc.pop();
}
return retStr;
}

f*w2014-03-06 08:03

16 楼

都是java的啊
我来个python的- -
class Solution:
def reverseWords(self, s):
words = s.split()
words.reverse()
return ' '.join(words)

f*w2014-03-06 08:03

17 楼

C++的
class Solution {
public:
void reverseWords(string &s) {
stack np;
size_t lastPos = s.find_first_not_of(" ", 0);
size_t pos = s.find_first_of(" ", lastPos);
while (string::npos != pos || string::npos != lastPos) {
if (lastPos != pos) {
string str = s.substr(lastPos, pos - lastPos);
np.push(str);
}
lastPos = s.find_first_not_of(" ", pos);
pos = s.find_first_of(" ", lastPos);
}
s = "";
while ((int)np.size() > 1) {
string str = np.top();
np.pop();
s += str + " ";
}
if ((int)np.size() > 0) s += np.top();
}
};

f*s2014-03-06 08:03

18 楼

class Solution {
public:
void reverseWords(string &s) {
stack ss;
istringstream is(s);
string word;

while(is>>word){
ss.emplace(word);
}

s = "";
while(!ss.empty()){
s += ss.top()+" ";
ss.pop();
}
if(s.length() > 0)
s.pop_back();
}
};

c*62014-03-06 08:03

19 楼

static String reverseWords(String s)
{
if(s.length() == 0) return s;
s += " ";
StringBuilder temp = new StringBuilder();
Stack stack = new Stack();
for(int i = 0; i < s.length(); i++)
{
char c = s.charAt(i);
if(c == ' ')
{
if(temp.length() > 0) stack.push(temp.toString());
temp = new StringBuilder();
}
else temp.append(c);
}
if(stack.isEmpty()) return "";
StringBuilder result = new StringBuilder();
while(!stack.isEmpty())
{
result.append(stack.pop());
if(!stack.isEmpty()) result.append(" ");
}
return result.toString();
}

b*s2014-03-06 08:03

20 楼

def solve(s):
return ' '.join(w for w in reversed(s.split()))

S*I2014-03-06 08:03

21 楼

乱棍打出去。:)

【在 b*********s 的大作中提到】

: def solve(s):
: return ' '.join(w for w in reversed(s.split()))

g*42014-03-06 08:03

22 楼

遇到不是space就把char存在临时的string里，遇到space就终止，把临时的string给存
了，什么额外的条件都无所谓
以下是C++
感觉OJ有问题，换了substr也出错
class Solution {
public:
void reverseWords(string &s) {
string ret = "";
for (int i = 0; i < s.length(); i++) {
string word = "";
while (!isspace(s[i])) {
word += s[i];
i++;
}
if (word.length() != 0) {
if (ret.length() == 0) {
ret = word;
}else {
ret = word + " " + ret;
}
}
}
s = ret;
}
};

l*y2014-03-06 08:03

23 楼

class Solution {
public:
void reverseWords(string &s) {
stack myStack;
string subString;
int head = 0;
int end = 0;
while(end != s.size())
{
if ((s[head] == ' ') && (s[end] == ' '))
{
head++;
end++;
}
else if (s[end] != ' ')
{
end++;
}
else
{
subString.assign(s, head, (end-head));
myStack.push(subString);
end++;
head = end;
}
}

if (head != end)
{
subString.assign(s, head, (end-head));
myStack.push(subString);
}

s.clear();
while (!myStack.empty())
{
subString = myStack.top();
myStack.pop();
s.append(subString);

if (myStack.empty())
{
break;
}

s.append(" ");
}
}
};

sp

【在 h*********2 的大作中提到】

: Given an input string, reverse the string word by word.
: For example,
: Given s = "the sky is blue",
: return "blue is sky the".
: 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 sp
: aces.

y*n2014-03-06 08:03

24 楼

新题就被这么多人破了处，作孽啊。

c*a2014-03-06 08:03

25 楼

在学新语言，第一次做题
def reverse(s: String)={val st = s.split(" ").reverse.foldRight("")(_+" "+_)
.dropRight(1);st}

p*o2014-03-06 08:03

26 楼

The idiomatic way:
In [1]: s = 'the sky is blue'
In [2]: ' '.join(reversed(s.split()))
Out[2]: 'blue is sky the'
Follow-up: OK, looks simple, but `s.split()` creates auxiliary space.
Can you do it in-place, i.e., with O(1) space?
为了迎合这样的变态要求，我们被迫要写下面这样C风格的所谓“算法”代码
In [9]: def swap_chars(s, iBgn, iEnd):
...: """ Reverse chars in buffer s ranging from iBgn to iEnd (
exclusive).
...: """
...: for i in range(iBgn, (iBgn+iEnd)//2):
...: j = iBgn + iEnd - i - 1
...: s[i], s[j] = s[j], s[i]
...:
...: def reverse_words(s):
...: """ Reverse all words in a sentence in-place.
...: """
...: n = len(s)
...:
...: # First pass, char-level reversal in the sentence
...: swap_chars(s, 0, n)
...:
...: # Second pass, char-level reversal in each word
...: i, j = 0, 1
...: while j < n:
...: if s[j] == ' ':
...: swap_chars(s, i, j)
...: i = j + 1
...: j += 2
...: else:
...: j += 1
...:
...: swap_chars(s, i, n) # last word
...:
In [10]: sbuff = list(s)
In [11]: reverse_words(sbuff)
In [12]: ''.join(sbuff)
Out[12]: 'blue is sky the'
如果结果只允许单空格分隔，可以在上述while循环中记录多余的空格数m，
再双指针扫描一次sbuff左移每个word，最后sbuff.pop() m次再join

sp

【在 h*********2 的大作中提到】

: Given an input string, reverse the string word by word.
: For example,
: Given s = "the sky is blue",
: return "blue is sky the".
: 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 sp
: aces.

t*52014-03-06 08:03

27 楼

你们这群禽兽。。。
def reverse(string):
return ' '.join(string.split()[::-1])

e*o2014-03-06 08:03

28 楼

perl:
0> join ' ', reverse split ' ', "the sky is blue ";
$res[0] = 'blue is sky the'

K*n2014-03-06 08:03

29 楼

大牛能看一下为什么我的解法有一个case总是超时呢？
public class Solution {
public String reverseWords(String s) {
String result = "";
Stack st = new Stack();
for (int i = s.length() -1; i >= 0; i--)
{
if (s.charAt(i) != ' ')
st.push(s.charAt(i));
else
{
while (!st.empty())
result += st.pop();
if (result.length() != 0 && result.charAt(result.length()-1)
!= ' ')
result += ' ';
}
}
while (!st.empty())
result += st.pop();
return result;
}
}

G*n2014-03-06 08:03

30 楼

没人用 string.split函数的吗。。。。。。。。

g*e2014-03-06 08:03

31 楼

class Solution {
public:
void reverseWords(string &s) {
for(int i=0; iif(s[i]==' ') {
if(i>0 && s[i-1]==' ' || i==0)
s.erase(i--, 1);
}
}
if(s[s.length()-1] == ' ')
s.erase(s.length()-1, 1);
reverse(s.begin(), s.end());
int st=0, end=0;
while(endif(s[end] == ' '){
reverse(s.begin()+st, s.begin()+end);
st=end+1;
}
end++;
}
reverse(s.begin()+st, s.end());
}
};

f*x2014-03-06 08:03

32 楼

感觉要是面试语言是Java就不会问这题了，用API简直等于没考点。

s*d2014-03-06 08:03

33 楼

用python,perl,API,stack的都在耍流氓好吗？这题就该用纯C做不许call库函数。。。
inplace, O(N) O(1)
class Solution {
private:
void DoReverse(string& w, int first, int last)
{
while(first < last)
{
swap(w[first++], w[last--]);
}
}

public:
void reverseWords(string &s) {
int ns = s.size();
int start=0, end = ns-1;
while(start < ns && s[start] == ' ') ++start;
while(end >=0 && s[end] == ' ') --end;
if(start > end)
{
s = "";
return;
}
else if(start == end)
{
s[0] = s[start];
s.resize(1);
return;
}
DoReverse(s, start,end);

int index = 0;
int left = 0;
while(start <= end)
{
if(s[start] != ' ')
{
s[index++] = s[start++];
if(start > end)
DoReverse(s, left, index-1);
}
else
{
DoReverse(s, left, index-1);
s[index++] = s[start++];
left = index;
while(start < end && s[start] == ' ') ++start;
}
}
s.resize(index);
}
};

j*x2014-03-06 08:03

34 楼

python这种语言的缺陷在这个one line code里面体现的颇为明显

【在 S**I 的大作中提到】

: 乱棍打出去。:)