JAVA - Several solutions - which do you think the best? It's appreciated if you could provided its pros and cons!!


  • 0
    N

    First

    public class Solution {
        public int firstUniqChar(String s) {
            Map<Character, Integer> map = new LinkedHashMap<>();
            List<Integer> indexs = new ArrayList<>();
            
            for (int i = 0; i < s.length(); i++) {
                char key = s.charAt(i);
                
                if (map.containsKey(key)) {
                    map.put(key, map.get(key) + 1);
                } else {
                    map.put(key, 0);
                    indexs.add(i);
                }
            }
            
            int i = 0;
            for (char key : map.keySet()) {
                if(map.get(key) == 0) {
                    return indexs.get(i);
                }
                i++;
            }
            return -1;
            
        }
    }
    

    Second

    public class Solution {
        public int firstUniqChar(String s) {
            
            if (s==null || s.isEmpty()) return -1;
            if (s.length() == 1) return 0;
            
            int[] counter = new int[s.length()];
            
            for (int i = 0; i < s.length(); i++) {
                if (counter[i] == 0) {
                    for (int j = i+1; j < s.length(); j++) {
                        if (s.charAt(i) == s.charAt(j)) {
                            counter[i] = 1;
                            counter[j] = 1;
                        }
                    }
                    if (counter[i] == 0) return i;
                }
            }
            return -1;
            
        }
    }
    

    Third

    public class Solution {
        public int firstUniqChar(String s) {
            
            if (s==null || s.isEmpty()) return -1;
            if (s.length() == 1) return 0;
            
            char[] counter = new char[s.length()];
            
            Map<Character, Boolean> map = new HashMap<>();
            
            for (int i=0; i < s.length(); i++) {
                char current = s.charAt(i);
                if (map.containsKey(current)) {
                    map.put(current, false);
                } else {
                    counter[i] = current;
                    map.put(current, true);
               }
            }
            
            for (int i=0; i < counter.length; i++) {
                if(counter[i] != 0) {
                    if(map.get(counter[i])) return i;
                }
            }
            return -1;
        }
    }
    

    Fourth

    public class Solution {
        public int firstUniqChar(String s) {
            
            if (s==null || s.isEmpty()) return -1;
            if (s.length() == 1) return 0;
            
            int[] counter = new int[26];
            
            int unpresent = 0;
            
            for (int i = 0; i < s.length(); i++) {
                int index = s.charAt(i) - 'a';
                if (counter[index] == unpresent){
                    counter[index] = i + 1;
                } else{
                    counter[index] = -1;
                }
            }
            
            int result = -1;
            
            for (int i : counter) {
                if (i > unpresent) {
                    if (result == -1) {
                        result = i;
                    } else if (i < result){
                        result = i;
                    }
                }
            }
            
            return result > 0 ? result -1 : result;
            
        }
    }
    

    Fifth

    public class Solution {
        public int firstUniqChar(String s) {
            char[] arr = s.toCharArray();
            if (arr.length == 1) return 0;
            int min = Integer.MAX_VALUE;
            int[] temp = new int[128];
            for (char c:arr) {
                temp[c]++;
            }
            for (int i= 'a'; i < temp.length;i++){
                if (temp[i] == 1)  min = Math.min(s.indexOf(i),min);
            }
            return min  == Integer.MAX_VALUE ? -1 : min;
        }
    }
    

    Sixth

    public int firstUniqChar(String s) {
            if(s==null || s.length()==0){
                return -1;
            }
            
            int[] bucket=new int[128];
            for(char c:s.toCharArray()){
                bucket[c]++;
            }
            for(int i=0;i<s.length();i++){
                if(bucket[s.charAt(i)]==1){
                    return i;
                }
            }
            return -1;
        }
    

  • 0
    N

    From the result of leetcode, the fifth one used the least time.

    But I don't really know why it's the best.
    (And I think there should be depended on the business scenario)

    And I think the method String.indexOf() shouldn't be used frequently.
    (And I have also check its source code, it will go through the under char array.)

    Could someone provide more analyse this?


  • 0
    J
    public class Solution {
        public int firstUniqChar(String s) {
            char[] chars = s.toCharArray();
            int[] index = new int[26];
            for( int i = 0; i < chars.length;i++){
                index[ chars[i] - 'a']++;
            }
            for( int i = 0; i < chars.length;i++){
                if( index[chars[i] - 'a'] == 1){
                    return i;
                }
            }
            return -1;
        }
    }
    

Log in to reply
 

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