Reverse words using O(1) extra space

A string may consist of multiple words. Each word in a C string can contain letters, numbers, or special symbols. Strings are considered storage elements for these characters. Each word is separated by a space character. Each word also forms a string of one character. In C, the reverse of any string is a string that follows −

• It is formed by taking characters from the end to the beginning.

• The length of the original string remains unchanged.

characters appear in a string can be easily reversed by swapping the characters at the beginning and end of the word.

Constant auxiliary space is represented by O(1), which means that the program does not require additional space during execution.

Some examples to illustrate the problem are as follows:

ExampleExample

Example 1 - str:Abc def

Output: cbA fed

Explanation: When reversing a string, the condition of the characters remains unchanged.

Example 2 - str: Hi spe2

Output: yeH 23%eps

The problem statement can be solved by extracting each word and maintaining a pair of start and end pointers for each word and then inverting it.

algorithm

• Step 1−Use a for loop to traverse the provided input string.

• Step 2- Use variable st to capture the starting character of the first word.

• Step 3− Once the first space is encountered, the lst variable is fixed on the previous character to mark the starting and ending characters of the word.

• Step 4− Using these two pointers and a while loop, reverse the characters of the word. On each iteration of the while loop, the pointer is moved to exhaust the string.

• Step 5− The values are updated to shift the pointers to the next subsequent word and so on. st is reinitialised to the next character after space.

• Step 6- The entire string is iterated and the corresponding words are reversed.

Example

The following C code snippet takes a string as input and reverses the words contained in it -

// including the required libraries #include  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:"<
        

         Copy after login
        
       

Output

original String:Reverse words Tutorials Point Reversed string : esreveR sdrow slairotuT tnioP

Space complexity

The space required by the above method is constant because there is no new initialization of any type of variables. No external space storage is required to swap words. All modifications are made in available storage variables.

in conclusion

Strings are composed of characters that can be arranged in any order or reversed by simple iteration. Since the algorithm performs a single iteration for the entire range of characters stored in it, the total time required is O(n), where n is the length of the string.

The above is the detailed content of Reverse words using O(1) extra space. For more information, please follow other related articles on the PHP Chinese website!