Sponsored
Sponsored
Using a two-pointer technique, we can efficiently reverse only the letters in the string. One pointer starts from the beginning and the other from the end. We swap letters when both pointers are on valid letters. If a pointer is on a non-letter, it moves until it finds a letter. The process continues until the two pointers meet or cross each other.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as we are modifying the string in place.
1class Solution:
2 def reverseOnlyLetters(self, s: str) -> str:
3 s = list(s)
4 left, right = 0, len(s) - 1
5 while left < right:
6 while left < right and not s[left].isalpha():
7 left += 1
8 while left < right and not s[right].isalpha():
9 right -= 1
10 if left < right:
11 s[left], s[right] = s[right], s[left]
12 left += 1
13 right -= 1
14 return ''.join(s)
15
16# Example usage
17sol = Solution()
18print(sol.reverseOnlyLetters("a-bC-dEf-ghIj"))This Python solution utilizes the isalpha() method of string objects to determine if a character is a letter. Two pointers are employed to toggle positions of the letters.
This approach uses a stack to collect all the letters in the string and then reinserts them in reverse order while iterating through the original string.
Time Complexity: O(n), for iterating through the string twice.
Space Complexity: O(n), for storing letter characters in the stack.
1function
This JavaScript function uses an array as a stack to push and pop letters, taking advantage of JavaScript's Array.prototype.push and Array.prototype.pop methods to manage the reversed sequence.