Java O(n) Easy To Understand, Optimal Solution


  • 0
    B

    Explanation
    The point to this question is to use two pointers, lo and hi. They are used to repeatedly identify and swap vowels.

    1. Initialize lo to 0, hi to s.length - 1; they denote the ends of our string
    2. Increment lo until the element at index lo is a vowel.
    3. Decrement hi until the element at index hi is a vowel.
    4. Swap elements at indices lo, hi. Increment lo, decrement hi.
    5. If lo < hi, repeat steps 2-5; otherwise, terminate and return our new string.

    Time Complexity
    The time complexity is O(n) where n is the length of s since we scan through its entire contents, swapping when necessary.

    class Solution {
        public boolean isVowel(char c) {
            c = Character.toLowerCase(c);
            return c == 'a' || c == 'e' || c == 'i' || 
                   c == 'o' || c == 'u';
        }
        
        public String reverseVowels(String s) {
            int lo = 0;
            int hi = s.length() - 1;
            char [] chS = s.toCharArray();
            
            // Perform swaps until halfway point
            while (lo < hi) {
                // Keep scanning left until vowel found
                while (lo < hi && !isVowel(chS[lo])) lo++;
                
                // Keep scanning right until vowel found
                while (lo < hi && !isVowel(chS[hi])) hi--;
                
                // Swap elements at indicex lo, hi
                char tmp = chS[lo];
                chS[lo] = chS[hi];
                chS[hi] = tmp;
                
                // Update lo, hi
                lo++; hi--;
            }
            return new String(chS);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.