資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 O(1) 額外空間反轉單個單詞
字串可能由多個單片語成。C++ 字串中的每個單詞可能包含字母、數字或特殊符號。字串被認為是這些字元的儲存元素。每個單詞由空格字元分隔。每個單詞也構成一個字元字串。C++ 中任何字串的反轉是指字串遵循以下幾點 -
它是從末尾到開頭獲取字元形成的。
原始字串的長度保持不變。
字串中字元的出現順序可以透過交換單詞開頭和結尾的字元輕鬆反轉。
常數輔助空間用 O(1) 表示，這意味著程式不需要額外的空間來完成其執行。
一些說明問題陳述的示例如下
示例
示例 1 - str : Abc def
輸出 : cbA fed
解釋：在反轉字串時，字元的大小寫保持不變。
示例 2 - str : Hey spe%32
輸出 : yeH 23%eps
可以透過提取單個單詞併為每個單詞維護一對起始和結束指標，然後對其進行反轉來解決問題陳述。
演算法
步驟 1 - 使用 for 迴圈遍歷提供的輸入字串。
步驟 2 - 使用變數 st 捕獲第一個單詞的起始字元。
步驟 3 - 一旦遇到第一個空格，lst 變數就會固定在前面的字元上，分別標記單詞的起始和結束字元。
步驟 4 - 使用這兩個指標和 while 迴圈，反轉該單詞的字元。在 while 迴圈的每次迭代中，指標都會移動以耗盡字串。
步驟 5 - 更新值以將指標移至下一個後續單詞，依此類推。st 重置為空格後的下一個字元。
步驟 6 - 遍歷整個字串，並以此方式反轉相應的單詞。
示例
以下 C++ 程式碼片段以字串作為輸入，並反轉其中包含的單詞 -
// including the required libraries
#include <bits/stdc++.h>
using namespace std;
//reversing current word of string
void reverseWord(string &st, int s, int e){
while (s < e) {
swap(st[s], st[e]);
s++;
e--;
}
}
//reverse the words of a string
string reverseString(string str){
int len = str.length();
//initialising the pointer with the first letter of the input string
int st = 0;
for (int i = 0; i <= len; i++) {
//stop the pointer at the first word
//either a space will be found indicating end of word or the string is finished
char ch = str[i];
if (ch == ' ' || i == len) {
//fetching the last character of the current word of the string
int lst = i - 1;
// Reverse the current word
reverseWord(str, st,lst);
//since the ith character is string , go to i+1 th character to fetch next word
st = i + 1;
}
}
return str;
}
//calling the method to reverse words
int main(){
//input string
string str = "Reverse words Tutorials Point";
cout<<"original String:"<<str;
//reversed string
string revstr = reverseString(str);
cout << "\nReversed string : "<< revstr;
return 0;
}
輸出
original String:Reverse words Tutorials Point Reversed string : esreveR sdrow slairotuT tnioP
空間複雜度
上述方法所需的空間是常數，因為沒有對任何型別的變數進行新的初始化。不需要外部儲存空間來交換單詞。所有修改都在可用的儲存變數中進行。
結論
字串由字元組成，可以透過簡單的字串迭代以任何順序排列或反轉。由於演算法對儲存在其內的字元的整個範圍執行單次迭代，因此所需的時間總計為 O(n)，其中 n 是字串的長度。
550 次瀏覽
