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.
原題：https://leetcode.com/PRoblems/longest-substring-without-repeating-characters/?tab=Description
分析： 題意應該已經默認了所有出現的字符均為ASCII字符集內。于是可以創建一個256個int型數的數組int dict[256]，用于記錄每一個字符最后一次出現的位置i, i ∈ [ 0, s.size() )，其中s為給定的字符串。定義maxLen為字串的最大長度，start為最大字串的下限，i為迭代數同時也最為最大字串的上限，最大字串范圍：( start, i ]。算法執行過程： 首先，start默認為-1，dict[256]初始化為-1，maxLen初始化為0。 其次，開始迭代過程，將字符串s從頭到尾讀一遍。如果發現有重復讀到的字符，則將start提升至該重復字符的第一個字符位置處。然后，不論上述條件是否成立，均將當前字符的最新位置存儲到dict[]中。最后計算當前無重復的字串是否比現有maxLen要大，如果是，則將maxLen的值替換為當前無重復字串的長度。以上步驟能得出正確結果，是因為它首先使用了當前字符s[i]在上一次出現的位置，( 即dict[ s[i] ]的值，如果dict[ s[i] ] != -1，則表明該字符s[i]出現過，是一個重復的字符，其次判斷s[i] > start，如果條件成立，則判斷重復字符位于當前定義的最長字串內，從而要更新當前定義的最長字串，方法是執行start = dict[ s[i] ]，) 然后再將當前s[i]的位置i覆蓋到dict[ s[i] ]中。 以下是代碼：class Solution {public: int lengthOfLongestSubstring(string s) { vector<int> dict(256, -1); int maxLen = 0, start = -1; for (int i = 0; i != s.length(); i++) { if (dict[s[i]] > start) start = dict[s[i]]; dict[s[i]] = i; maxLen = max(maxLen, i - start); } return maxLen; }};注：這個算法引用自： https://leetcode.com/problems/longest-substring-without-repeating-characters/?tab=Solutions （2.C++ code in 9 lines.）
新聞熱點
疑難解答
