Friday, April 19, 2024 8:59 EDT

Leetcode 345. Reverse Vowels of a String (Easy)

Approach
I think there are two ways to approach this one.

The first, creating a singular loop that moves forward but also create a secondary variable to iterate backward through the same loop. This would not be a double for-loop, as the conditions in the for-loop are only forward moving. Then you would only need to iterate through half the string and swap when vowels are found.

The second which is my solution below is to create a list of the vowels in backwards order by doing a single for-loop. This is seemingly more complex but the inner loop will onyl run in the worst-case 10 times and is purely for verifying if the char is a vowel.

Then, we loop one more time to swap each vowel with the correct char in vowels.

v = vowels in english alphabet
vowels = string of vowels from input string in reverse order
l = input string length
vs = vector size (probably could have hard coded this to 10 to save some time)
k = iterator for char (vowel) to be inserted from "vowels"

Complexity
Time Complexity: O(n)
Space Complexity: O(n)

Code

class Solution {
public:
    string reverseVowels(string s) {
        vector<char> v({'a','e','i','o','u','A','E','I','O','U'});
        string vowels;
        int l = s.length();
        int vs = v.size();
        for(int i = l; i >= 0; i--){
            for(int j = 0; j < vs; j++){
                if(s[i] == v[j]){
                    vowels += s[i];
                    break;
                }
            }
        }
        int k=0;
        for(int i = 0; i < l; i++){
            for(int j = 0; j < vs; j++){
                if(s[i] == v[j]){
                    s[i] = vowels[k];
                    k++;
                    break;
                }
            }
        }
        return s;
    }
};