Java Standard Two Pointer Solution


  • 68
    N

    In the inner while loop, don't forget the condition "start less than end" while incrementing start and decrementing end. This is my friend's google phone interview question. Cheers!
    // update! May use a HashSet<Character> to reduce the look up time to O(1)

    public class Solution {
    public String reverseVowels(String s) {
        if(s == null || s.length()==0) return s;
        String vowels = "aeiouAEIOU";
        char[] chars = s.toCharArray();
        int start = 0;
        int end = s.length()-1;
        while(start<end){
            
            while(start<end && !vowels.contains(chars[start]+"")){
                start++;
            }
            
            while(start<end && !vowels.contains(chars[end]+"")){
                end--;
            }
            
            char temp = chars[start];
            chars[start] = chars[end];
            chars[end] = temp;
            
            start++;
            end--;
        }
        return new String(chars);
    }
    

    }


  • 20
    E

    Same idea. But use statically declared String as the dictionary and use the indexOf function to avoid String comparison. This code run in 6ms.

    public class Solution {
    static final String vowels = "aeiouAEIOU";
    public String reverseVowels(String s) {
        int first = 0, last = s.length() - 1;
        char[] array = s.toCharArray();
        while(first < last){
            while(first < last && vowels.indexOf(array[first]) == -1){
                first++;
            }
            while(first < last && vowels.indexOf(array[last]) == -1){
                last--;
            }
            char temp = array[first];
            array[first] = array[last];
            array[last] = temp;
            first++;
            last--;
        }
        return new String(array);
    }
    

    }


  • 2
    N

    Yes! Actually, our ideas are exactly the same since string.contains() method is implemented by string.indexOf(). Of course, if we use a hashset to reduce the look up time to O(1), but there are just 10 characters, I think we are fine :)


  • -1
    Y
    	public static boolean[] vowels = new boolean[300];
    	static{
    		vowels['a'] = true;
    		vowels['o'] = true;
    		vowels['e'] = true;
    		vowels['i'] = true;
    		vowels['u'] = true;
    		vowels['A'] = true;
    		vowels['O'] = true;
    		vowels['E'] = true;
    		vowels['I'] = true;
    		vowels['U'] = true;
    	}
        public String reverseVowels(String s) {
        	if (s == null){
        		return null;
        	}
        	
            char[] arr = s.toCharArray();
            int maxIndex = arr.length - 1;
            int i = maxIndex, j = 0;
            while (i > j) {
            	while (i>=0 && !vowels[arr[i]]){
            		i--;
            	}
            	
            	while (j <= maxIndex && !vowels[arr[j]]){
            		j++;
            	}
            	
            	if (i>= 0 && j <= maxIndex && i > j ){
            		char tmp = arr[i];
    	        	arr[i] = arr[j];
    	        	arr[j] = tmp;
    	        	i--;
    	        	j++;
            	}
            }
            
            
            return new String(arr);
        }
    

  • 0
    P

    Can we use stack for this? push the vowels found in the string into the stack. And then iterate over the sentence again and pop whenever you encounter a vowel. so you will have them reversed. But somehow it doesnt work for me.


  • 0
    B

    I used a set to store the characters but honestly, with such a small number of characters, the overhead of the Set may actually make it slower.

    Edit: I tried and it does make it faster but only reduced runtime from about 19ms to 16ms.


  • 9
    M

    The last sample code is close to what I established while solving the problem. Firstly, using a boolean array to store the state of each character (weather it is a vowel or not) may require more memory than using a String, but it is far more efficient if numerous test cases are to be run. That is because the array provides direct access to an element, whereas searching over and over the vowels string will slow down the program if the input string is very long. That said, both cases will use constant memory, but the array approach is faster. My solution manages at 4ms.

    The ASCII table has 256 characters we should account for. While searching the input string, we use two pointers (from the begging and from the end). All we have to do is make sure we stop iterating when they become equal in value.

    public static boolean[] vowels = new boolean[256];
    static{
        vowels['a'] = true;
        vowels['o'] = true;
        vowels['e'] = true;
        vowels['i'] = true;
        vowels['u'] = true;
        vowels['A'] = true;
        vowels['O'] = true;
        vowels['E'] = true;
        vowels['I'] = true;
        vowels['U'] = true;
    }
    
    public String reverseVowels(String s) {
        if(s == null || s.isEmpty()) {
            return "";
        }
        int i,j;
        i = 0;
        j = s.length() - 1;
        char[] str = s.toCharArray();
        while(i < j) {
            while(i < j && !vowels[str[i]]) i++;
            while(i < j && !vowels[str[j]]) j--;
            if(i < j) {
                char temp = str[i];
                str[i] = str[j];
                str[j] = temp;
                i++;
                j--;
            }
        }
        return String.valueOf(str);
    }

  • 1
    N

    Try this! But since we traverse the string twice, the running time doubles. Good Luck!

        public class Solution {
        public String reverseVowels(String s) {
            if(s == null || s.length()==0){
                return s;
            }
            HashSet<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');
            
            // reverse the  vowels while popping up
            Stack<Character> vStack = new Stack<>();
            for(char c : s.toCharArray()){
                if(vowels.contains(c)){
                    vStack.push(c);
                }
            }
            
            StringBuilder sb = new StringBuilder();
            for(char c : s.toCharArray()){
                if(vowels.contains(c)){
                    sb.append(vStack.pop());
                }else{
                    sb.append(c);
                }
            }
            
            return sb.toString();
        }
    }

  • 0
    P

    Oh this is great! Thank you.. Also if we are traversing it twice, wouldnt it still be O(n)? thanks


  • 0
    N

    Yes! Big O is Still O(n) :)


  • 0
    P

    :) Thank you


  • 0
    H

    my solution is that use Set and 2 pointers

    public String reverseVowels(String s) {
        if(s == null || s.length() == 0)
            return s;
        char[] sa = s.toCharArray();
        Set<Character> set = new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        set.add('A');
        set.add('E');
        set.add('I');
        set.add('O');
        set.add('U');
        int left = 0, right = sa.length - 1;
        while(left < right) {
            if(!set.contains(sa[left]))
                left++;
            else if(!set.contains(sa[right]))
                right--;
            else {
                char temp = sa[left];
                sa[left] = sa[right];
                sa[right] = temp;
                left++;
                right--;
            }
        }
        return new String(sa);
    }

  • 2
    M

    Conceptually, your approach does not differ from mine. However, it would be slower for the following 2 reasons:

    1. Hash tables of any kind require a mathematical function to estimate the table index. This is not that costly in this case, but it is still slower than direct access in an array.
    2. The add and contains require the use of the the has function; contains also leads to an internal to the hash table iteration over conflicting entries that have the same index returned by the hash function.

  • 0
    P
    This post is deleted!

  • 1
    A

    My 6ms solution

        public String reverseVowels(String s) {
            if (s.length() == 0) return s;
            char[] arr = s.toCharArray();
            int low = 0;
            int high = arr.length - 1;
            while (low < high) {
                if (!isVowel(arr[low]) && !isVowel(arr[high])) {
                    low++;
                    high--;
                } else if (!isVowel(arr[low])) {
                    low++;
                } else if (!isVowel(arr[high])) {
                    high--;
                } else {
                    char temp = arr[low];
                    arr[low] = arr[high];
                    arr[high] = temp;
                    low++;
                    high--;
                }
            }
            return new String(arr);
        }
    
        private boolean isVowel(char ch) {
            ch = Character.toLowerCase(ch);
            return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
        }

  • 0

    What i recommend to you is to read the algorithm book first. That is the fundamental thing. Do not worry to take exercises. ^^


  • 0
    R
    This post is deleted!

  • 0
    C

    Nice solution! Following solution with similar idea could be used to avoid checking i<j in inner while loops. I think that does not affect time complexity of solution. Correct me if I am wrong.

    public String reverseVowels(String s) {
    if (null==s) return s;

        final char[] word = s.toCharArray();
        
        int i = 0;
        int j = word.length - 1;
        
        while(i<j){
            if(!isVowel(word[i])){
                i++;
                continue;
            }
            if(!isVowel(word[j])){
                j--;
                continue;
            }
            swap(word, i++, j--);
        }
        
        return new String(word);
    }
    
    private void swap(final char[] word, final int i, final int j){
        final char temp = word[i];
        word[i] = word[j];
        word[j] = temp;
    }
    
    private boolean isVowel(final char ch){
        switch(Character.toLowerCase(ch)){
            case 'a':
            case 'e':
            case 'i':
            case 'o':
            case 'u':
                return true;
            default: return false;
        }
    }
    

  • 0
    D
    public class Solution {
        public String reverseVowels(String s) {
            Set<Character> se = new HashSet<Character>();
            
             se.add('a');
             se.add('e');
             se.add('i');
             se.add('o');
             se.add('u');
                  se.add('A');
             se.add('E');
             se.add('I');
             se.add('O');
             se.add('U');
             StringBuilder vowel = new StringBuilder(); 
             for(char c: s.toCharArray())
             {
                 if(se.contains(c))
                  vowel.append(c);
             }
             vowel.reverse();
              int i=0;
                       StringBuilder output = new StringBuilder(); 
    
                for(char c: s.toCharArray())
             {
                 if(se.contains(c))
                   output.append(vowel.charAt(i++));
                   else
                    output.append(c);
             }
             return output.toString();
        }
    }

  • 0

    @Praneetha17 I think using stack is gonna work. I used a list. every time i found a vowel in string, i added this vowel at the beginning of the list

    list.add(0, vowel);
    

    Then at the second loop, every time there is a vowel, i remove the first element in the list

    list.remove(0);
    

    This is actually the same idea as stack


Log in to reply
 

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