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.
1using System;
2
3class Solution {
4 public string ReverseOnlyLetters(string s) {
5 char[] arr = s.ToCharArray();
6 int left = 0, right = s.Length - 1;
7 while (left < right) {
8 while (left < right && !char.IsLetter(arr[left])) left++;
9 while (left < right && !char.IsLetter(arr[right])) right--;
10 if (left < right) {
11 char temp = arr[left];
12 arr[left++] = arr[right];
13 arr[right--] = temp;
14 }
15 }
16 return new string(arr);
17 }
18
19 static void Main(string[] args) {
20 Solution sol = new Solution();
21 Console.WriteLine(sol.ReverseOnlyLetters("a-bC-dEf-ghIj"));
22 }
23}In this C# version, the char.IsLetter() method is used to ascertain character letter status. A simple swapping between pointers accomplishes the reversal of 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.
1import
This Java solution uses a Stack to record all letters and a StringBuilder to reconstruct the string with reversed letters. The stack's LIFO property allows reversing the letters' order naturally.