0387._first_unique_character_in_a_string.md

Navigation

• Navigation
• Links
• Solution 1 哈希表
• Solution 2 对比左右索引

Links

1. https://leetcode.com/problems/first-unique-character-in-a-string/
2. https://leetcode-cn.com/problems/first-unique-character-in-a-string/

Solution 1 哈希表

    时间复杂度：O(N)
    空间复杂度：O(N)

class Solution:
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        memo = {}

        for c in s:
            memo[c] = memo.get(c, 0) + 1
        
        for idx, c in enumerate(s):
            if memo[c] == 1:
                return idx

        return -1

---

func firstUniqChar(s string) int {
	cnt := make(map[rune]int, len(s))
	for _, ch := range s {
		cnt[ch]++
	}
	for i, ch := range s {
		if cnt[ch] == 1 {
			return i
		}
	}
	return -1
}

---

Go

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

Solution 2 对比左右索引

注意事项：您可以假定该字符串只包含小写字母。 分别从目标的字符串头和字符串尾查找对应字母的索引；如果两索引相等，则说明是单一字符。

    时间复杂度：O(N)。遍历ascii_lowercase为常数级别，find()和rfind()为O(N)
    空间复杂度：O(1)

from string import ascii_lowercase

class Solution:
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        min_index = len(s)

        # 时间复杂度为常数级别
        for c in ascii_lowercase:   
            i = s.find(c)
            if i != -1 and i == s.rfind(c):
                min_index = min(i, min_index)
            
        return min_index if min_index != len(s) else -1