尋找最長不重復子串

afishhhhh 發布于2019-07-25 12:03 / 1213人閱讀

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

尋找最長不重復子串 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.

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

遍歷字符串，過程中將出現過的字符存入字典，key為字符，value為字符下標

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

用start保存最長子串的開始下標

如果字符已經出現在字典中，更新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地址

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/38655.html

JS算法題之leetcode(1~10)

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

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

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

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

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

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

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

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

摘要：題目解析題目含義很簡單，即求出沒有字符重復的子字符串的長度。例如很明顯就是個由完全重復字符組成的字符串，所以它的答案長度為。所以綜合來看該算法的效率為。題目 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