LeetCode 3——無重復字符的最長子串

Rocture 發(fā)布于2019-07-31 11:16 / 1231人閱讀

摘要：題目解答方法一我們從前往后遍歷字符串，代表最長子串的起始位置，一開始設置為零。如果沒有遇到重復字符，則更新子串的長度，向后遍歷。最長子串的起始位置重復的字符在子串中的位置初始化映射自動初始化為零獲取更多精彩，請關注

1. 題目

2. 解答 2.1. 方法一

我們從前往后遍歷字符串，start 代表最長子串的起始位置，一開始設置為零。

如果沒有遇到重復字符，則更新子串的長度，向后遍歷。

如果遇到重復字符時，則更新字符串起始位置為上一個相同字符的后面一個位置，同時更新子串長度。

重復上面這個過程，直到遍歷完畢。

"abcabc"，start = 0，str_len = 1, 2, 3
此時第二次遇到 "a"，start = 1，str_len = 3
此時第二次遇到 "b"，start = 2，str_len = 3
此時第二次遇到 "c"，start = 3，str_len = 3

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        max_len = 0
        str_len = 0
        start = 0      # 最長子串的起始位置
        index = 0     # 上一個相同字符在子串中的位置，是一個相對位置，不是在原字符串中的位置
        
        for i in range(len(s)):
            
            if (s[i] not in s[start:i]):
                str_len += 1
               
            # 如果遇到重復字符，更新子串的起始位置為上一個相同字符的后面一個位置
            # 同時我們需要更新子串長度
            else:
                max_len = max(max_len, str_len)
                index = s[start:i].find(s[i])
                str_len = str_len - index
                start = start + index + 1 
                
        max_len = max(max_len, str_len) # 一直沒有遇到重復字符
        return max_len

2.2. 方法二

方法一中，我們每次判斷當前字符是否為重復字符時，都需要在子串中進行搜索，更新子串起始位置時，也要在子串中搜索上一個相同字符的位置，效率很低。

其實我們需要知道的就是一個子串的起始位置，然后往后遍歷的時候只需要在適當?shù)臅r候更新這個起始位置重新計算子串長度即可。

因此，我們可以建立一個當前字符和當前字符下一個位置的映射。

所有映射全部初始化為零，start = 0。從前往后開始遍歷字符串，同時更新映射，計算子串長度。

如果當前字符的映射大于 start，說明在 satrt 后面出現(xiàn)過當前字符，就更新 start。

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_len = 0
        str_len = 0
        start = 0    # 最長子串的起始位置
        index = 0   # 重復的字符在子串中的位置
        
        # 初始化映射
        table = []
        for i in range(128):
            table.append(0)
                
        for i in range(len(s)):
            
            start =  max(start, table[ord(s[i])])

            str_len = i - start + 1    
            max_len = max(max_len, str_len)
            
            table[ord(s[i])] = i + 1
            
        return max_len

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        int table[128] = {0}; // 自動初始化為零
        int max_len = 0;
        int str_len = 0;
        int start = 0;
        
        string::iterator it = s.begin();
            
        for (int j = 0; it != s.end(); it++, j++)
        {
            start = start > table[*it] ? start : table[*it];
            table[*it] = j + 1;
            str_len = j - start + 1;
            max_len = max_len < str_len ? str_len : max_len;
        }
        
        return max_len;
    }
};

獲取更多精彩，請關注「seniusen」!

云服務器 GPU云服務器最長公共子串 java最長相同子串字符串找子串算法字符串最大子串c語言

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/44912.html

LeetCode3.無重復字符的最長子串JavaScript

摘要：示例輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。請注意，你的答案必須是子串的長度，是一個子序列，不是子串。 LeetCode3.無重復字符的最長子串JavaScript 給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。示例 1: 輸入: abcabcbb輸出: 3 解釋: 因為無重復字符的最長子串是 abc，所以其長度為 3。示例 2: 輸入: bbbbb輸出...

vboy1010 2019-08-23 14:46 評論0 收藏0
【leetcode】3. 無重復字符的最長子串

摘要：示例輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。請注意，你的答案必須是子串的長度，是一個子序列，不是子串。完成循環(huán)后取隊列中出現(xiàn)的最大長度即可。給定一個字符串，請你找出其中不含有重復字符的?最長子串?的長度。示例?1：輸入: abcabcbb 輸出: 3 解釋: 因為無重復字符的最長子串是 abc，所以其長度為 3。示例 2：輸入: bbbbb 輸出: 1 解釋:...

qc1iu 2019-08-23 18:32 評論0 收藏0
LeetCode.3 無重復字符的最長子串(JS)

摘要：先跳到第三題是因為第二題第一眼沒讀懂一題目無重復字符的最長子串給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。示例輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。以此來實現(xiàn)判斷是否包含重復字符。先跳到第三題是因為第二題第一眼沒讀懂一、題目無重復字符的最長子串：給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。示例1 輸入: abcabcbb輸...

wthee 2019-08-23 16:18 評論0 收藏0
leetcode 無重復字符的最大子串

摘要：示例輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。請注意，你的答案必須是子串的長度，是一個子序列，不是子串。臨時存儲子串存儲最長子串如果子串中不存在如果子串中存在重復字符的位置截取字符串給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。示例 1: 輸入: abcabcbb 輸出: 3 解釋: 因為無重復字符的最長子串是 abc，所以其長度為 3。示例 2...

laoLiueizo 2019-08-23 13:49 評論0 收藏0
力扣(LeetCode)3

摘要：示例輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。請注意，你的答案必須是子串的長度，是一個子序列，不是子串。若沒有重復元素，則區(qū)間右邊擴大，否則區(qū)間左邊縮小。題目地址：https://leetcode-cn.com/probl...題目描述：給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。示例 1: 輸入: abcabcbb輸出: 3 解釋: 因為無重復字符...

_DangJin 2019-08-16 15:43 評論0 收藏0