387. First Unique Character in a String

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> mp;
        for(char c:s) mp[c]++;
        int n = s.size();
        for(int i=0;i<n;++i){
            if(mp[s[i]] == 1) return i;
        }
        return -1;
    }
};
  • vector
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
    public:
        int firstUniqChar(string s) {
            vector<int> vec(26,0);
            for(char c:s) vec[c-'a']++;
            int n = s.size();
            for(int i=0;i<n;++i){
                if(vec[s[i] - 'a'] ==1) return i;
            }
            return -1;
        }
    };

analysis

  • time complexity O(n)
  • space complexity O(1) 最多26字母