387. 字符串中的第一个唯一字符

题目描述

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例 1：

输入: s = "leetcode"
输出: 0

示例 2:

输入: s = "loveleetcode"
输出: 2

示例 3:

输入: s = "aabb"
输出: -1

提示:

1 <= s.length <= 10⁵
s 只包含小写字母

解法

方法一：计数

我们用一个哈希表或者一个长度为 \(26\) 的数组 \(\text{cnt}\) 来存储每个字符出现的次数，然后从头开始遍历每个字符 \(\text{s[i]}\)，如果 \(\text{cnt[s[i]]}\) 为 \(1\)，则返回 \(i\)。

遍历结束后，如果没有找到符合条件的字符，返回 \(-1\)。

时间复杂度 \(O(n)\)，其中 \(n\) 是字符串的长度。空间复杂度 \(O(|\Sigma|)\)，其中 \(\Sigma\) 是字符集，本题中字符集为小写字母，所以 \(|\Sigma|=26\)。

Python3JavaC++GoTypeScriptJavaScriptPHP

class Solution:
    def firstUniqChar(self, s: str) -> int:
        cnt = Counter(s)
        for i, c in enumerate(s):
            if cnt[c] == 1:
                return i
        return -1

class Solution {
    public int firstUniqChar(String s) {
        int[] cnt = new int[26];
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        for (int i = 0; i < n; ++i) {
            if (cnt[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
}

class Solution {
public:
    int firstUniqChar(string s) {
        int cnt[26]{};
        for (char& c : s) {
            ++cnt[c - 'a'];
        }
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (cnt[s[i] - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
};

func firstUniqChar(s string) int {
    cnt := [26]int{}
    for _, c := range s {
        cnt[c-'a']++
    }
    for i, c := range s {
        if cnt[c-'a'] == 1 {
            return i
        }
    }
    return -1
}

function firstUniqChar(s: string): number {
    const cnt = new Map<string, number>();
    for (const c of s) {
        cnt.set(c, (cnt.get(c) || 0) + 1);
    }
    for (let i = 0; i < s.length; ++i) {
        if (cnt.get(s[i]) === 1) {
            return i;
        }
    }
    return -1;
}

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function (s) {
    const cnt = new Map();
    for (const c of s) {
        cnt.set(c, (cnt.get(c) || 0) + 1);
    }
    for (let i = 0; i < s.length; ++i) {
        if (cnt.get(s[i]) === 1) {
            return i;
        }
    }
    return -1;
};

class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function firstUniqChar($s) {
        for ($i = 0; $i < strlen($s); $i++) {
            $hashtable[$s[$i]]++;
        }
        for ($i = 0; $i < strlen($s); $i++) {
            if ($hashtable[$s[$i]] == 1) {
                return $i;
            }
        }
        return -1;
    }
}

387. 字符串中的第一个唯一字符

题目描述

解法

方法一：计数

评论