Compare three java solutions


  • 0
    P

    there are three solutions of java with a little difference and different performance.

    1. using HashSet :time 13ms
    public String reverseVowels(String s) {
            int size = s.length();
            char[] ori= s.toCharArray();
            int left = 0,right = size-1;
            HashSet<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');
            char tmp;
            while(left <right){
                if(!set.contains(ori[left])){
                    left++;continue;
                }
                if(!set.contains(ori[right])){
                    right--;continue;
                }
                tmp = ori[left];
                ori[left]=ori[right];
                ori[right] = tmp;
                left++;right--;
            }
            return String.valueOf(ori);
        }
    
    1. using Array traversal :time 6ms
    char[] vow = {'a','e','i','o','u','A','E','I','O','U'};
        public String reverseVowels(String s) {
            int size = s.length();
            char[] origin= s.toCharArray();
            int left = 0,right = size-1;
            char tmp;
            while(left <right){
                if(ucontains(origin[left])){
                    left++;continue;
                }
                if(ucontains(origin[right])){
                    right--;continue;
                }
                tmp = origin[left];
                origin[left]=origin[right];
                origin[right] = tmp;
                left++;right--;
            }
            return String.valueOf(ori);
        }
        private boolean ucontains(char cc){
            for(char a:vow){
                if(cc==a)return false;
            }
            return true;
        }
    

    3.using hardcode :time 5ms

    public String reverseVowels(String s) {
            int size = s.length();
            char[] origin= s.toCharArray();
            int left = 0,right = size-1;
            char tmp;
            while(left <right){
                if(!contains(origin[left])){
                    left++;continue;
                }
                if(!contains(origin[right])){
                    right--;continue;
                }
                tmp = origin[left];
                origin[left]=origin[right];
                origin[right] = tmp;
                left++;right--;
            }
            return String.valueOf(ori);
        }
        private boolean contains(char cc){
            return cc=='a'||cc=='e'||cc=='i'||cc=='o'||cc=='u'||cc=='A'||cc=='E'||cc=='I'||cc=='O'||cc=='U';
        }
    

    the result shows method-3 is the fastest one.
    the analysis follows.
    1.the number of elements to be match is small (only 10).
    2.the function of contains in HashSet will calculate index with complex algorithm,such as bitwise operation,mod operation.this will cost more time comparing with simple traversal .
    3.the Array 'origin' in method-2 is stored in heap of JVM, so there will be some time cost when fetch value from it. But method-3(hardcode) will do the match action in Method Area directly.


Log in to reply
 

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