[Leetcode] Longest Substring Without Repeating Cha

FleyX 發布于2019-08-14 12:18 / 2895人閱讀

摘要：哈希表是最自然的想法。在遍歷字符串時，我們先根據哈希表找出該字符上次出現的位置，如果大于等于子字符串首，便更新子字符串首。結束后，將該字符新的位置放入哈希表中。

Longest Substring Without Repeating Characters 最新更新解法：https://yanjia.me/zh/2018/12/...

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

哈希表雙指針法 Hash Table with Two Pointers 復雜度

時間O(n) 空間O(1) 字符種類數有限

思路

根據最長不重復子字符串的定義，我們在遍歷字符串時一旦遇到當前子字符串中已有字符，那么新的子字符串應該從這個重復點的下一位開始。所以為了在一次遍歷中就能找出最大長度，我們需要記錄兩個東西。第一是某個字母是否在當前子字符串中出現過，第二是如果出現過那它在字符串中的位置是什么。而最簡單的判斷某個字符是否在當前子字符串中出現過的方法，就是看它上次出現的位置是在當前子字符串第一個字符的前面還是后面，所以我們只要記錄該字符上次出現的位置就可以同時滿足這兩個要求。哈希表是最自然的想法。在遍歷字符串時，我們先根據哈希表找出該字符上次出現的位置，如果大于等于子字符串首，便更新子字符串首。因為這里相當于上一個子字符串已經結束，我們還要更新最大長度。結束后，將該字符新的位置放入哈希表中。

注意

遍歷完成后還要有一次額外的更新最大長度的操作，以處理最長字符串在末尾的情況。

新的子字符串的起點應該是重復元素的下標加一

字符串問題要注意處理空字符串的特例

所記錄的上次出現位置大于等于lowerBound時就需要更新了，注意這個last >= lowerBound

代碼

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        Map table = new HashMap();
        int lowerBound = 0, max = 1;
        for(int i = 0; i < s.length(); i++){
            Character c = s.charAt(i);
            Integer last = table.get(c);
            if(last != null && last >= lowerBound){
                max = Math.max(i - lowerBound, max);
                lowerBound = last + 1;
            }
            table.put(c, i);
        }
        return Math.max(s.length() - lowerBound, max);
    }
}

2018/2

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        characters = {}
        startIndex = 0
        endIndex = 0
        maxLen = 0
        while endIndex < len(s):
            c = s[endIndex]
            maxLen = max(maxLen, endIndex - startIndex)
            if c in characters and characters[c] >= startIndex:
                startIndex = characters[c] + 1
            characters[c] = endIndex
            endIndex = endIndex + 1
        maxLen = max(maxLen, endIndex - startIndex)
        return maxLen

后續 Follow Up

Q: 能否不用哈希表完成本題？
A：可以將哈希表換成和字符一一映射的數組。如果是ASCII字符集，可以初始化一個256個元素的數組，數組的下標對應于字符的ASCII碼，而數組的內容則是每個字符上次出現的位置。

GPU云服務器云服務器 Repeating Without Longest LeetCode

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

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

[LeetCode] Longest Substring Without Repeating Cha

Problem 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...

graf 2019-08-19 10:52 評論0 收藏0
[LeetCode] Longest Substring Without Repeating Cha

摘要：建立數組，存儲個字符最近一次出現的位置。首次出現某字符時，其位置標記為，并用無重復字符計數器記錄無重復字符的長度，再在更新其最大值。循環完整個字符串后，返回最大值。 Problem Given a string, find the length of the longest substring without repeating characters. Examples: Given ...

CoderStudy 2019-08-14 15:48 評論0 收藏0
leetcode 3 Longest Substring Without Repeating Cha

摘要：題目詳情題目要求輸入一個字符串，我們要找出其中不含重復字符的最長子字符串，返回這個最長子字符串的長度。對于字符串中的每一個字符，先判斷中是否已經存在這個字符，如果不存在，直接將添加到，如果已存在，則新的字符串就從不含前一個字符的地方開始。題目詳情 Given a string, find the length of the longest substring without repe...

xcold 2019-08-15 14:21 評論0 收藏0
[LintCode] Longest Substring Without Repeating Cha

摘要：哈希表法雙指針法只有當也就是時上面的循環才會結束，，跳過這個之前的重復字符再將置為 Problem Given a string, find the length of the longest substring without repeating characters. Example For example, the longest substring without repeat...

Scliang 2019-08-14 15:19 評論0 收藏0
[Leetcode]Longest Substring Without Repeating Char

摘要：解題思路本題借助實現。如果字符未出現過，則字符，如果字符出現過，則維護上次出現的遍歷的起始點。注意點每次都要更新字符的位置最后返回時，一定要考慮到從到字符串末尾都沒有遇到重復字符的情況，所欲需要比較下和的大小。 Longest Substring Without Repeating CharactersGiven a string, find the length of the lon...

awesome23 2019-08-16 10:26 評論0 收藏0