Sponsored
Sponsored
The two pointers approach involves using two indices, one starting at the beginning and the other at the end of the string. You check and swap vowels as they are encountered using these pointers, moving them inward toward each other. This method is efficient as it requires a single pass through the string, with each character processed a maximum of two times.
Time Complexity: O(n), where n is the length of the string, as each character is processed at most twice.
Space Complexity: O(1) as no additional space is used aside from variables.
1def reverseVowels(s: str) -> str:
2 vowels = set('aeiouAEIOU')
3 s = list(s)
4 left, right = 0, len(s) - 1
5 while left < right:
6 while left < right and s[left] not in vowels:
7 left += 1
8 while left < right and s[right] not in vowels:
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)This Python solution uses a set for vowel lookup and a list to hold the string for mutable operations. Two pointers move from both ends to find and swap vowels where necessary.
This approach uses a stack to collect all vowels in the string as they are encountered in a single pass. Then, it makes a second pass through the string to replace vowels, using the stack to supply the reversed vowels. This approach is straightforward but might not be as time efficient as the two pointers approach.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n) for storing vowels separately.
1using System.Collections.Generic;
public class Solution {
public string ReverseVowels(string s) {
List<char> vowels = new List<char>();
foreach (var c in s) {
if ("aeiouAEIOU".IndexOf(c) >= 0) {
vowels.Add(c);
}
}
char[] arr = s.ToCharArray();
int index = vowels.Count - 1;
for (int i = 0; i < arr.Length; i++) {
if ("aeiouAEIOU".IndexOf(arr[i]) >= 0) {
arr[i] = vowels[index--];
}
}
return new String(arr);
}
}In C#, we use a List to store vowels and a char array to manipulate and replace characters in the string. The stored vowels are used in reverse order to ensure correct swapping.