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

一、引子

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

二、題目

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

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

1、思路

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

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

2、編程實(shí)現(xiàn)

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
        
        # 用字典記錄各字符的索引。如果重復(fù)出現(xiàn)，則索引值需要加上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

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

本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！

審核編輯 黃昊宇