Python – Reverse String except punctuations

Given a string with punctuations, perform string reverse, leaving punctuations at their places.

Input : test_str = ‘neveropen@#for&%%gee)ks’ 
Output : skeeg@#rof&%%ske)eg 
Explanation : Whole string is reversed, except the punctuations.

Input : test_str = ‘neveropen@#for&%%gee)ks’ [ only substring reversal ] 
Output : skeeg@#rof&%%eeg)sk 
Explanation : Only substrings are reversed. 
 

Method #1 : Using loop + stack  + punctuation + split()

In this, we use stack to perform string reversal, checking for punctuation, if current character is one, we append that. The split method is used to handle cases of spaces, which needs to be ignored while reverse.

The original string is :neveropen#for&%%gee)ks
The Reversed String ignoring punctuation : skeeg#rof&%%ske)eg 

The time complexity is O(n), where n is the length of the input string.

The auxiliary space is also O(n), where n is the length of the input string. 

Method #2 : Using groupby() + isalnum() [ for substring specific reversal ]

In this, we form grouping of each of substring between punctuations and reverse them among them, not whole. The isalnum() is used to check for all the alphabets.

The Time and Space Complexity for all the methods are the same:

Time Complexity: O(n²)

Space Complexity: O(n)

Using Two Pointers in python:

Approach:

Create an empty string res and a list of the punctuation characters punc.
Traverse the input string s using two pointers i and j, initialized to the beginning and end of the string, respectively.
While i < j, check if s[i] and s[j] are both alphabetic characters. If they are, swap them.
If s[i] or s[j] is a punctuation character, skip that character and do not move the pointer.
If s[i] and s[j] are both non-alphabetic characters, append them to res without swapping.
Continue steps 3-5 until i >= j.
Return res.

sgke)eeekgs#  %%&rfo

Time Complexity: O(n), where n is the length of the input string s. This is because we traverse the string only once.
Auxiliary Space: O(n), where n is the length of the input string s, because we create a new string to store the reversed string.

METHOD 4:USING def .

APPROACH:

In this approach, we first split the input string into words using the split() method. For each word, we initialize two pointers left and right that point to the beginning and end of the word, respectively. We then use a while loop to iterate over the characters of the word, swapping characters at the left and right pointers if they are both letters. We also increment left and decrement right until they cross over or one of them encounters a punctuation character. After reversing the word, we update the word list with the reversed word. Finally, we join the words back together with spaces using the join() method and return the resulting string.

ALGORITHM:

1.Initialize a string containing all the punctuations.
2.Split the input string into a list of words.
3.Iterate through each word in the list.
4.Initialize two pointers, left and right, to the first and last characters of the word respectively.
5.While the left pointer is less than the right pointer, do the following:
      a.If the character at the left pointer is a punctuation mark, move the left pointer to the next character.
      b.If the character at the right pointer is a punctuation mark, move the right pointer to the previous character.
      c.If both characters at the left and right pointers are not punctuation marks, swap them and move the left pointer to the next character and the right pointer to the previous character.
6.Replace the original word with the modified word in the list.
7.Join the list of words back into a string and return it as the result.

skeeg@#rof&%%ske)eg

The time complexity of this approach is O(n^2), where n is the length of the input string, since we potentially iterate over each character in each word. 

The auxiliary space is O(n), since we split the input string into a list of words.