LeetCode初級算法--字符串02：字符串中的第一個唯一字符

一、引子

這是由LeetCode官方推出的的經典面試題目清單~
這個模塊對應的是探索的初級算法~旨在幫助入門算法。我們第一遍刷的是leetcode推薦的題目。

二、題目

給定一個字符串，找到它的第一個不重復的字符，并返回它的索引。如果不存在，則返回 -1。

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

1、思路

首先我們可以想到這道題需要的是一個不重復的字符，我們順序找到第一個不重復的字符，把其索引存起來，返回最小的索引也就是第一個不重復的字符了。

注：使用count方法，會增加時間復雜度，所以我們用字典記錄各字符的索引。如果重復出現，則索引值需要加上len(s)，小于len(s)的那個索引就是我們求的值。

2、編程實現

python

class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        #算法超時
        # res = []
        # for i in s:
        #     if s.count(i) == 1:
        #         res.append(s.index(i))
        # if len(res):
        #     return min(res)
        # return -1
        
        # 用字典記錄各字符的索引。如果重復出現，則索引值需要加上len(s)
        d = {}
        for i in range(len(s)):
            if s[i] not in d:
                d[s[i]] = i
            else:
                d[s[i]] += len(s)
        
        if len(s) and min(d.values()) < len(s) :
            return min(d.values())
        return -1

分享技術，樂享生活：我們的公眾號計算機視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關注！

本文由博客一文多發平臺 OpenWrite 發布！

審核編輯 黃昊宇