leetcode 387. First Unique Character in a String（字符串中第一个独一无二的字母）

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

Input: s = “leetcode”
Output: 0
Example 2:

Input: s = “loveleetcode”
Output: 2
Example 3:

Input: s = “aabb”
Output: -1

找出字符串s 中只出现一次的字母，返回它的index。
如果没有，返回-1。

思路：

网上有个1ms的解法，用到了字符串自带的indexOf, lastIndexOf函数，
如果它俩相等，证明只出现了一次，更新最小的index即可。

public int firstUniqChar(String s) {
    int result=s.length();
    
    for(char c='a';c<='z';c++){
        int firstIndex=s.indexOf(c);
        if(firstIndex!=-1 && firstIndex==s.lastIndexOf(c)){
            result=Math.min(result, firstIndex);
        }
    }
    
    return result==s.length()?-1:result;
}
1
2
3
4
5
6
7
8
9
10
11
12

这里我们不用字符串自带的函数，
因为字母只有26个，所以用一个数组记录下每个字母出现的次数，
然后找到次数为1的字母，它出现的最小index即可，

找最小index岂不是又要把s 遍历一次？no,
还是用一个数组记录下每个字母出现的最小index,
直接找到对应的index, 然后更新最小的index即可。

public int firstUniqChar(String s) {
    int[] cnt = new int[26];
    int[] firstIdx = new int[26];
    int res = s.length();
        
    Arrays.fill(firstIdx, -1);
    
    for(int i = 0; i < s.length(); i++) {
        int idx = s.charAt(i) - 'a';
        cnt[idx] ++;
        if(firstIdx[idx] == -1) firstIdx[idx] = i;
    }
    
    for(int i = 0; i < 26; i++) {
        if(cnt[i] == 1) res = Math.min(res, firstIdx[i]);
    }
    
    return (res == s.length() ? -1 : res);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19