【leetcode刷題】20T3-無重複字元的最長子串

  • 2020 年 2 月 16 日
  • 筆記

木又同學2020年第3篇解題報告

leetcode第3題:無重複字元的最長子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters


【題目】

給定一個字元串,請你找出其中不含有重複字元的 最長子串 的長度。

示例 1:  輸入: "abcabcbb"  輸出: 3  解釋: 因為無重複字元的最長子串是 "abc",所以其長度為 3。    示例 2:  輸入: "bbbbb"  輸出: 1  解釋: 因為無重複字元的最長子串是 "b",所以其長度為 1。    示例 3:  輸入: "pwwkew"  輸出: 3  解釋: 因為無重複字元的最長子串是 "wke",所以其長度為 3。       請注意,你的答案必須是 子串 的長度,"pwke" 是一個子序列,不是子串。  

【思路】

可以暴力求解,對於每一個子串,判斷是否有重複字元。判斷是否有重複字元,需要O(n),所以總的時間複雜度為O(n^3)

我們想想,有很多子串是沒有必要判斷的,比如對於"dvdf",當知道「dvd」是重複子串時,「dvdf」肯定是重複子串。因此,我們使用i表示非重複子串起始下標,j用於遍曆數組,當s[j]存在於s[i:j]中,說明s[i:j+1]是重複子串,s[i:j]是以i為起點的最長非重複子串,然後更改i為s[i:j]中與s[j]相同的元素的下標。

【程式碼】

python版本

class Solution(object):      def lengthOfLongestSubstring(self, s):          """          :type s: str          :rtype: int          """          # 窗口i->j          i = 0          res = 0          for j in range(i+1, len(s)):              # 如果有重複字元,比較res和前一段非重複字元串長度,並更改i              if s[j] in s[i:j]:                  res = max(res, j-i)                  i += s[i:j].index(s[j]) + 1          # 不要忘了,最後要比較res和len(s)-i          res = max(res, len(s)-i)          return res  

C++版本

class Solution {  public:      int lengthOfLongestSubstring(string s) {          int i = 0;          int res = 0;          for (int j=i+1; j < s.size(); j++){              // s[i:j]中是否存在s[j]              // 存在比較長度,且更新i              int offset = s.substr(i, j-i).find(s[j]);              if (offset >= 0){                  res = max(res, j-i);                  i += offset + 1;              }          }          // 不要忽略最後一段子串          int tmp = s.size() - i;          res = max(res, tmp);          return res;      }  };