Description
Given a string s, reverse only all the vowels in the string and return it.
The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.
Examples:
Example 1:
Input: s = "IceCreAm"
Output: "AceCreIm"
Explanation:
The vowels in s are ['I', 'e', 'e', 'A']. On reversing the vowels, s becomes "AceCreIm".
Example 2:
Input: s = "leetcode"
Output: "leotcede"Solution in Python
Approach:
- Two-pointer technique:
- We can use two pointers, one starting at the beginning (
left) of the string and the other at the end (right). - These pointers will move toward each other. When both pointers point to vowels, we swap them. Otherwise, we move the pointers inward (i.e., skip over non-vowel characters).
- Once the two pointers cross, all vowels will have been reversed in place.
- We can use two pointers, one starting at the beginning (
- Helper functions and checks:
- We define a helper function or use a set of vowels (
{'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}) to easily check if a character is a vowel. - Strings are immutable in Python, so we will convert the string to a list of characters for easier manipulation and then convert it back to a string at the end.
- We define a helper function or use a set of vowels (
Python
class Solution:
def reverseVowels(self, s: str) -> str:
# Define a set of vowels for quick lookup
vowels = set('aeiouAEIOU')
# Convert string to list of characters (since strings are immutable)
s = list(s)
# Initialize two pointers
left, right = 0, len(s) - 1
# Loop until the two pointers cross
while left < right:
# Move left pointer to the next vowel
while left < right and s[left] not in vowels:
left += 1
# Move right pointer to the previous vowel
while left < right and s[right] not in vowels:
right -= 1
# Swap the vowels at left and right pointers
s[left], s[right] = s[right], s[left]
# Move both pointers inward
left += 1
right -= 1
# Convert list back to a string and return
return ''.join(s)Explanation:
- Vowel Set:
- We define a set
vowelscontaining all the lowercase and uppercase vowels for quick lookups (O(1)average time complexity).
- We define a set
- Convert String to List:
- Since Python strings are immutable, we convert the string
sinto a list of characters so that we can modify individual elements (swap vowels).
- Since Python strings are immutable, we convert the string
- Two-Pointer Approach:
- Left pointer starts at the beginning of the string and right pointer starts at the end.
- We skip non-vowel characters by moving the pointers inward until both point to vowels.
- Once both
leftandrightpoint to vowels, we swap the characters at these positions. - Continue moving the pointers inward until they cross each other.
- Join and Return:
- After processing, the list is converted back into a string using
''.join(s)and returned as the final result.
- After processing, the list is converted back into a string using
Solution in C++
C++
class Solution {
public:
string reverseVowels(string s) {
// Define a set of vowels (both lowercase and uppercase)
unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
// Two pointers approach: left starts from the beginning, right from the end
int left = 0, right = s.length() - 1;
// Traverse the string until the two pointers meet
while (left < right) {
// Move left pointer forward until we find a vowel
while (left < right && vowels.find(s[left]) == vowels.end()) {
left++;
}
// Move right pointer backward until we find a vowel
while (left < right && vowels.find(s[right]) == vowels.end()) {
right--;
}
// Swap the vowels at the left and right pointers
if (left < right) {
swap(s[left], s[right]);
left++;
right--;
}
}
// Return the modified string with vowels reversed
return s;
}
};Solution in Javascript
JavaScript
var reverseVowels = function(s) {
// Step 1: Define vowels (both lowercase and uppercase)
const vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
// Step 2: Convert the string into an array to modify characters by index
let arr = s.split('');
// Step 3: Use two-pointer approach
let left = 0; // Starting pointer
let right = arr.length - 1; // Ending pointer
// Step 4: Iterate over the string until the two pointers meet
while (left < right) {
// Move left pointer forward until it finds a vowel
while (left < right && !vowels.has(arr[left])) {
left++;
}
// Move right pointer backward until it finds a vowel
while (left < right && !vowels.has(arr[right])) {
right--;
}
// Step 5: Swap the vowels found at the left and right pointers
if (left < right) {
// Swap the characters
let temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
// Move the pointers inward after swapping
left++;
right--;
}
}
// Step 6: Join the array back into a string and return the result
return arr.join('');
};Solution in Java
Java
class Solution {
public String reverseVowels(String s) {
// Step 1: Define a set of vowels (both lowercase and uppercase)
// We use a HashSet for O(1) lookup time.
Set<Character> vowels = new HashSet<>();
vowels.add('a');
vowels.add('e');
vowels.add('i');
vowels.add('o');
vowels.add('u');
vowels.add('A');
vowels.add('E');
vowels.add('I');
vowels.add('O');
vowels.add('U');
// Step 2: Convert the input string into a character array for easier manipulation.
char[] chars = s.toCharArray();
// Step 3: Use two pointers to scan the array from both ends
int left = 0;
int right = chars.length - 1;
// Step 4: Loop until the two pointers meet
while (left < right) {
// Move the left pointer forward until we find a vowel
while (left < right && !vowels.contains(chars[left])) {
left++;
}
// Move the right pointer backward until we find a vowel
while (left < right && !vowels.contains(chars[right])) {
right--;
}
// Step 5: If both pointers are at vowels, swap them
if (left < right) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
// Move the pointers inward after swapping
left++;
right--;
}
}
// Step 6: Convert the character array back into a string and return the result
return new String(chars);
}
}