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.
1#include <stdio.h>
2#include <ctype.h>
3#include <string.h>
4
5char* reverseOnlyLetters(char* s) {
6 int left = 0, right = strlen(s) - 1;
7 while (left < right) {
8 while (left < right && !isalpha(s[left])) {
9 left++;
10 }
11 while (left < right && !isalpha(s[right])) {
12 right--;
13 }
14 if (left < right) {
15 char temp = s[left];
16 s[left] = s[right];
17 s[right] = temp;
18 left++;
19 right--;
20 }
21 }
22 return s;
23}
24
25int main() {
26 char str[] = "a-bC-dEf-ghIj";
27 printf("%s\n", reverseOnlyLetters(str));
28 return 0;
29}This C function uses two pointers to reverse letters in a string. The isalpha() function checks for letters, and strlen() gives the length to set the right pointer. A simple swap operation is done when both pointers point to 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.
1#include <iostream>
2#include <stack>
#include <cctype>
std::string reverseOnlyLetters(std::string s) {
std::stack<char> letters;
for (char c : s) {
if (isalpha(c)) letters.push(c);
}
for (char &c : s) {
if (isalpha(c)) {
c = letters.top();
letters.pop();
}
}
return s;
}
int main() {
std::string s = "a-bC-dEf-ghIj";
std::cout << reverseOnlyLetters(s) << std::endl;
return 0;
}The C++ solution utilizes the STL std::stack to store and reverse English letters in the string. The stack allows for easy access to reverse the order of letters during reinsertion.