数据结构
网络
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 次浏览
