LeetCode | Reverse Words in a String
タイトル:
Given an input string, reverse the string word by word.
For example, Given s = "
考え方:方法1:まず文を語からなるものと見なし、例えば「A B C」とするので、文のすべての文字を前後に交換することができます.「C'B'A'」が得られる.明らかにX'は逆順の語Xを表すので、第2のステップは各語の文字列を前後に交換することである.プロセス全体の時間的複雑度はO(n)、空間的複雑度はO(1)である.この方法の欠点は、文字列列に連続したスペースがあり、文字列の先頭にスペースがあるなど、多くの特殊な状況を考慮していないことである.
方法2:2つのstackを用いて,1つは単語を表し,1つは文を表す.スペース以外の文字に遭遇した場合、単語stackを入れます.スペースに遭遇した場合、単語stackの文字を文stackに押し込み(単語が逆順序になっていることに注意)、スペースを1つだけ追加します.最後に文stackを順次出力します.この場合、文は逆順になります.2回の逆序の道理は同じ方法である.
コード:メソッド1:
方法2:
Given an input string, reverse the string word by word.
For example, Given s = "
the sky is blue
", return "blue is sky the
". 考え方:方法1:まず文を語からなるものと見なし、例えば「A B C」とするので、文のすべての文字を前後に交換することができます.「C'B'A'」が得られる.明らかにX'は逆順の語Xを表すので、第2のステップは各語の文字列を前後に交換することである.プロセス全体の時間的複雑度はO(n)、空間的複雑度はO(1)である.この方法の欠点は、文字列列に連続したスペースがあり、文字列の先頭にスペースがあるなど、多くの特殊な状況を考慮していないことである.
方法2:2つのstackを用いて,1つは単語を表し,1つは文を表す.スペース以外の文字に遭遇した場合、単語stackを入れます.スペースに遭遇した場合、単語stackの文字を文stackに押し込み(単語が逆順序になっていることに注意)、スペースを1つだけ追加します.最後に文stackを順次出力します.この場合、文は逆順になります.2回の逆序の道理は同じ方法である.
コード:メソッド1:
class Solution {
public:
void reverseWords(string &s) {
int begin = 0;
int end = 0;
while(end < s.size()){
if(s[end] == ' '){
swapString(s, begin, end - 1);
begin = end+1;
end = begin;
}
else{
end++;
}
}
swapString(s, begin, end - 1);
swapString(s, 0, s.size()-1);
}
void swapString(string &s, int begin, int end){
while(end > begin){
char c = s[begin];
s[begin] = s[end];
s[end] = c;
begin++;
end--;
}
}
};
方法2:
class Solution {
public:
void reverseWords(string &s) {
stack<int> word;
stack<int> sentence;
int i = 0;
while(i <= s.size()){
if(i == s.size() || s[i] == ' '){
if(!word.empty()){
if(!sentence.empty()){
sentence.push(' ');
}
while(!word.empty()){
sentence.push(word.top());
word.pop();
}
}
} else{
word.push(s[i]);
}
i++;
};
s.clear();
while(!sentence.empty()){
s.push_back(sentence.top());
sentence.pop();
};
}
};