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.
1using System;
2using System.Collections.Generic;
class Solution {
public string ReverseOnlyLetters(string s) {
Stack<char> letters = new Stack<char>();
foreach (char c in s) {
if (char.IsLetter(c)) {
letters.Push(c);
}
}
char[] result = new char[s.Length];
for (int i = 0; i < s.Length; i++) {
if (char.IsLetter(s[i])) {
result[i] = letters.Pop();
} else {
result[i] = s[i];
}
}
return new string(result);
}
static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.ReverseOnlyLetters("a-bC-dEf-ghIj"));
}
}This C# solution employs a Stack to collect letters, leveraging its LIFO order to invert the sequence of letters during the final reconstruction.