Reverse Words in a String
https://github.com/Max-Liu/Leetcode-in-golang/blob/master/reverse-words-in-a-string/main.go
import (
"fmt"
"strings"
)
func main() {
str := "the sky is blue 111"
fmt.Println(reverseWordsInAString(str))
}
func reverseWordsInAString(str string) (finalStr string) {
strSlice := strings.Split(str, " ")
strLen := len(strSlice)
var halfStrSlice []string
if strLen%2 == 0 {
halfStrSlice = strSlice[:strLen/2]
} else {
halfStrSlice = strSlice[:(strLen-1)/2]
}
for key, value := range halfStrSlice {
temp := value
strSlice[key] = strSlice[strLen-key-1]
finalStr = finalStr + strSlice[strLen-key-1] + " "
strSlice[strLen-key-1] = temp
}
for _, value := range strSlice[len(halfStrSlice):] {
finalStr += value + " "
}
return finalStr
}
[LeetCode] Reverse Words in a String II | 程序员达达
跟Reverse Words in a String很类似，但是这里要求in-place，也就是说不需要开辟额外空间。
该题在LeetCode中假设开头和结尾没有空格，而且单词之间只有一个空格。但其实不需要这些假设也是可以的，就是代码会比较复杂。
思路就是两步走，第一步就是将整个字符串翻转。然后从头逐步扫描，将每个遇到单词再翻转过来。
[注意事项]
1）如果是Java，应该跟面试官指出String是immutable，所以需要用char array来做。
2）follow-up问题：k-step reverse。也就是在第二部翻转的时候，把k个单词看作一个长单词，进行翻转。
一开始对方先简单的介绍自己, 然后轮到我简单的介绍自己, 接着挑了一个自己的项目介绍.
紧接着是算法. 对方先出了一道题, 问我见过没有. 我表示我见过... (Word break LC原题) 于是对方又换了一道题 (Reverse Words in a String II 还是LC原题). 但是这次就没有问我做过没有了, 简单讲解思路后麻利的写完, 并且写了简单的case测试. 途中也讨论了特殊情况并且印证结果 (比如leading & trailing space的处理). Follow up是加入符号但是reverse的时候需要保留位置. 我大概讲了一下想到的两种思路, 不是最优, 并且由于时间不够, 也没有写完. 面试官最后提了一下最优思路(用Double Stack)并且让我问了几个问题后就结束了.
http://betterpoetrythancode.blogspot.com/2015/02/reverse-words-in-string-ii-leetcode.html
Read full article from [LeetCode] Reverse Words in a String II | 程序员达达
Given an input string, reverse the string word by word.
For example,
Given s = "
return "
Given s = "
the sky is blue",return "
blue is sky the".- 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.
- 题目大意：给定一个字符串，对字符串进行逆转。
- 解题思路：看到这道题目有两种思路：
X. 1）用两个指针从前到后扫描，分开单词，先对每个单词进行逆转，最后再对整个字符串逆转；
比如题目中给的例子：先对每个单词进行逆转得到的结果："eht yks si eulb"，然后再整体逆转即可得到"blue is sky the"。
X. 2）根据空格切分字符串，将切分得到的单词存到vector中，然后将vector中的单词从末尾开始输出即可。
在衡量了两种方法之后，觉得第二种方法代码更加简洁方便，便选择了第二种思路。
public String reverseWords(String s) { if (s == null || s.length() == 0) { return ""; } // split to words by space String[] arr = s.split(" "); StringBuilder sb = new StringBuilder(); for (int i = arr.length - 1; i >= 0; --i) { if (!arr[i].equals("")) { sb.append(arr[i]).append(" "); } } return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1); }
void reverseWords(string &s) { string ret; int j = s.size(); for(int i=s.size()-1; i>=0; i--) { if(s[i]==' ') j = i; else if(i==0 || s[i-1]==' ') { if(!ret.empty()) ret.append(" "); ret.append(s.substr(i, j-i)); } } s = ret; }
public String reverseWords(String s) {
String[] a = s.split(" ");
StringBuilder sb = new StringBuilder();
for (int i = a.length - 1; i >= 0; i--) {
if (!a[i].equals("")) {
sb.append(a[i]);
sb.append(" ");
}
}
if (sb.length() > 1)
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
public String reverseWords(String s) {
StringBuilder reversed = new StringBuilder();
int j = s.length();
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == ' ') {
j = i;
}
else if (i == 0 || s.charAt(i - 1) == ' ') {
if (reversed.length() != 0)
reversed.append(' ');
reversed.append(s.substring(i, j)); // substring is not efficient
}
}
return reversed.toString();
}
public String reverseWords(String s) {
char a[] = s.toCharArray();
reverse(a, 0, a.length);
for (int i = 0, j = 0; j <= a.length; j++) {
if (j == a.length || a[j] == ' ') {
reverse(a, i, j);
i = j + 1;
}
}
return new String(a);
}
private void reverse(char[] s, int begin, int end) {
for (int i = 0; i < (end - begin) / 2; i++) {
char temp = s[begin + i];
s[begin + i] = s[end - i - 1];
s[end - i - 1] = temp;
}
}
GoLang:https://github.com/Max-Liu/Leetcode-in-golang/blob/master/reverse-words-in-a-string/main.go
import (
"fmt"
"strings"
)
func main() {
str := "the sky is blue 111"
fmt.Println(reverseWordsInAString(str))
}
func reverseWordsInAString(str string) (finalStr string) {
strSlice := strings.Split(str, " ")
strLen := len(strSlice)
var halfStrSlice []string
if strLen%2 == 0 {
halfStrSlice = strSlice[:strLen/2]
} else {
halfStrSlice = strSlice[:(strLen-1)/2]
}
for key, value := range halfStrSlice {
temp := value
strSlice[key] = strSlice[strLen-key-1]
finalStr = finalStr + strSlice[strLen-key-1] + " "
strSlice[strLen-key-1] = temp
}
for _, value := range strSlice[len(halfStrSlice):] {
finalStr += value + " "
}
return finalStr
}
[LeetCode] Reverse Words in a String II | 程序员达达
跟Reverse Words in a String很类似，但是这里要求in-place，也就是说不需要开辟额外空间。
该题在LeetCode中假设开头和结尾没有空格，而且单词之间只有一个空格。但其实不需要这些假设也是可以的，就是代码会比较复杂。
思路就是两步走，第一步就是将整个字符串翻转。然后从头逐步扫描，将每个遇到单词再翻转过来。
[注意事项]
1）如果是Java，应该跟面试官指出String是immutable，所以需要用char array来做。
2）follow-up问题：k-step reverse。也就是在第二部翻转的时候，把k个单词看作一个长单词，进行翻转。
public void reverseWords(char[] s) { reverse(s, 0, s.length); for (int i=0, j=0; j<=s.length; j++) { if (j==s.length || s[j]==' ') { reverse(s, i, j); i = j + 1; } } } private void reverse(char [] s, int begin, int end) { for (int i=0; i<(end-begin)/2; i++) { char temp = s[begin+i]; s[begin+i] = s[end-i-1]; s[end-i-1] = temp; } }https://www.cnblogs.com/EdwardLiu/p/4306561.html
这道题要求in-place做法，不能使用extra space, 那么，做法跟Rotate Array那道题非常相似
（1）reverse the whole array
（2）reverse each subarray seperated by ' '
注意不要忘了reverse最后一个word
1 public void reverseWords(char[] s) { 2 // Three step to reverse 3 // 1, reverse the whole sentence 4 reverse(s, 0, s.length - 1); 5 // 2, reverse each word 6 int start = 0; 7 int end = -1; 8 for (int i = 0; i < s.length; i++) { 9 if (s[i] == ' ') { 10 reverse(s, start, i - 1); 11 start = i + 1; 12 } 13 } 14 // 3, reverse the last word, if there is only one word this will solve the corner case 15 reverse(s, start, s.length - 1); 16 } 17 18 public void reverse(char[] s, int start, int end) { 19 while (start < end) { 20 char temp = s[start]; 21 s[start] = s[end]; 22 s[end] = temp; 23 start++; 24 end--; 25 } 26 }http://www.1point3acres.com/bbs/thread-132725-1-1.html
一开始对方先简单的介绍自己, 然后轮到我简单的介绍自己, 接着挑了一个自己的项目介绍.
紧接着是算法. 对方先出了一道题, 问我见过没有. 我表示我见过... (Word break LC原题) 于是对方又换了一道题 (Reverse Words in a String II 还是LC原题). 但是这次就没有问我做过没有了, 简单讲解思路后麻利的写完, 并且写了简单的case测试. 途中也讨论了特殊情况并且印证结果 (比如leading & trailing space的处理). Follow up是加入符号但是reverse的时候需要保留位置. 我大概讲了一下想到的两种思路, 不是最优, 并且由于时间不够, 也没有写完. 面试官最后提了一下最优思路(用Double Stack)并且让我问了几个问题后就结束了.
Read full article from [LeetCode] Reverse Words in a String II | 程序员达达
