leetcode解题: First Unique Character in a String (387)

发表于 | 分类于

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = “leetcode”
return 0.

s = “loveleetcode”,
return 2.
Note: You may assume the string contain only lowercase letters.

解法1：HashTable

思路是将字符串建立hashtable，其中存的是每一个字符出现的位置，如果出现超过1次则位置设置为-1，然后遍历hashtable找出最小的非-1的即可。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> map;
        for (int i = 0; i < s.size(); ++i) {
            if (map.find(s[i]) != map.end()) {
                map[s[i]] = -1;
            } else {
                map[s[i]] = i;
            }
        }
        int res = s.size();
        for (auto iter = map.begin(); iter != map.end(); ++iter) {
            if (iter->second !=-1) {
                res = min(res, iter->second);
            }
        }
        if (res == s.size()) return -1;
        else return res;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!map.containsKey(ch)) {
                map.put(ch, new ArrayList<Integer>());
            }
            map.get(ch).add(i);
        }
        int res = Integer.MAX_VALUE;
        for (char key : map.keySet()) {
            if (map.get(key).size() == 1) {
                res = Math.min(res, map.get(key).get(0));
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

解法2：HashTable

上面的思路有点繁复，如果hashtable中存入每一个字符出现的次数，那么只需要重新扫描一遍字符串，找到第一个次数为1的就是所求的答案。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> map;
        for (char c : s) {
            ++map[c];
        }
        for (int i = 0; i < s.size(); i++) {
            if (map[s[i]] == 1) {
                return i;
            }
        }
        return -1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (map.get(ch) == 1) {
                return i;
            }
        }
        return -1;
    }
}