尋找最長不重復(fù)子串

afishhhhh 發(fā)布于2019-07-25 12:03 / 1222人閱讀

摘要：尋找最長不重復(fù)子串思路時間復(fù)雜度為遍歷字符串，過程中將出現(xiàn)過的字符存入字典，為字符，為字符下標(biāo)用保存遍歷過程中找到的最大不重復(fù)子串的長度用保存最長子串的開始下標(biāo)如果字符已經(jīng)出現(xiàn)在字典中，更新的值如果字符不在字典中，更新的值代碼本題以及其它

尋找最長不重復(fù)子串 Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

思路(時間復(fù)雜度為O(n))

遍歷字符串，過程中將出現(xiàn)過的字符存入字典，key為字符，value為字符下標(biāo)

用maxLength保存遍歷過程中找到的最大不重復(fù)子串的長度

用start保存最長子串的開始下標(biāo)

如果字符已經(jīng)出現(xiàn)在字典中，更新start的值

如果字符不在字典中，更新maxLength的值

return maxLength

代碼

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start = maxLength = 0
        usedChar = {}

        for i in range(len(s)):
            if s[i] in usedChar and start <= usedChar[s[i]]:
                start = usedChar[s[i]] + 1
            else:
                maxLength = max(maxLength, i - start + 1)
            usedChar[s[i]] = i

        return maxLength

本題以及其它leetcode題目代碼github地址: github地址

云服務(wù)器 GPU云服務(wù)器最長公共子串 java最長相同子串尋找重復(fù)數(shù)字 c語言隨機抽取不重復(fù)

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/38655.html

相關(guān)文章

JS算法題之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一個字符，判斷正負(fù)符號，若是英文直接返回，若數(shù)字則不取?；匚臄?shù)題目描述判斷一個整數(shù)是否是回文數(shù)?；匚臄?shù)是指正序從左向右和倒序從右向左讀都是一樣的整數(shù)。 JS算法題之leetcode(1~10) 前言一直以來，前端開發(fā)的知識儲備在數(shù)據(jù)結(jié)構(gòu)以及算法層面是有所暫缺的，可能歸根于我們的前端開發(fā)的業(yè)務(wù)性質(zhì)，但是我認(rèn)為任何的編程崗位都離不開數(shù)據(jù)結(jié)構(gòu)以及算法。因此，我作為...

SoapEye 2019-08-26 10:44 評論0 收藏0
動態(tài)規(guī)劃問題（2）——尋找最長公共子串

摘要：題目給定兩個字符串求出它們的最長公共字串說明比如在單詞和它們的最長公共子序列是。最長公共子串和最長公共子序列的區(qū)別。題目給定兩個字符串,求出它們的最長公共字串 var str1=abcdefg; var str2=xyzabcd; 說明：比如在單詞abcdefg和abcdefg它們的最長公共子序列是abcd。尋找最長子序列常用于遺傳學(xué)中，用于使用核苷酸堿基的首字母對DNA的描述（這...

wushuiyong 2019-08-21 11:27 評論0 收藏0
網(wǎng)易2018校招前端筆試題解析

摘要：現(xiàn)在有一個給定的字符串中每個字符代表小易的某個磚塊的顏色。例如那么小易有六種排列的結(jié)果其中只有和滿足最多只有一對不同顏色的相鄰磚塊。輸入描述輸入包括一行四個整數(shù)以空格分割輸出描述輸出一個整數(shù)表示小易最多能獨立生活多少天。前言：注意，網(wǎng)易校招筆試在?？途W(wǎng)進行，在這里使用js完成算法題時，不要寫一個function() {}就認(rèn)為完成了題目，那樣通過率是0%(題主就是這樣，估計筆試掛了。...

Baoyuan 2019-08-21 11:56 評論0 收藏0
前端中等算法-無重復(fù)字符的最長子串

摘要：無重復(fù)字符的最長子串難度中等描述給定一個字符串，請你找出其中不含有重復(fù)字符的最長子串的長度。輸入輸出解釋因為無重復(fù)字符的最長子串是，所以其長度為。無重復(fù)字符的最長子串難度：中等描述：給定一個字符串，請你找出其中不含有重復(fù)字符的最長子串的長度。樣例：輸入: abcabcbb 輸出: 3 解釋: 因為無重復(fù)字符的最長子串是 abc，所以其長度為 3。輸入: bbbbb ...

hyuan 2019-08-26 10:40 評論0 收藏0
Leecode-3 Longest Substring Without Repeating Char

摘要：題目解析題目含義很簡單，即求出沒有字符重復(fù)的子字符串的長度。例如很明顯就是個由完全重復(fù)字符組成的字符串，所以它的答案長度為。所以綜合來看該算法的效率為。題目 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: abcabcbbO...

luzhuqun 2019-08-16 13:49 評論0 收藏0