快捷導(dǎo)航

Python3 無(wú)重復(fù)字符的最長(zhǎng)子串的實(shí)現(xiàn)

更新時(shí)間：2019年10月08日 14:47:33 作者：Joy_917

這篇文章主要介紹了Python3 無(wú)重復(fù)字符的最長(zhǎng)子串的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

題目：

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。

示例：

示例 1:
輸入: “abcabcbb”
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 “abc”，所以其長(zhǎng)度為 3。

示例 2:
輸入: “bbbbb”
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 “b”，所以其長(zhǎng)度為 1。

示例 3:
輸入: “pwwkew”
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 “wke”，所以其長(zhǎng)度為 3。
請(qǐng)注意，你的答案必須是子串的長(zhǎng)度，“pwke” 是一個(gè)子序列，不是子串。

思路：

這道題會(huì)很自然的想到暴力解法，就是按位遞增依次檢查子串是否重復(fù)，并記下目前最大的子串長(zhǎng)度，如果重復(fù)就從下一位索引處的字符開始重新檢查。下面是代碼實(shí)現(xiàn)：

class Solution:
 def lengthOfLongestSubstring(self, s: str) -> int:
 # 最長(zhǎng)子串的長(zhǎng)度
 max_len = 0
 # 存放字符的字典
 char_dict = {}
 index = 0
 while s[index:].__len__() >= max_len:
  # 當(dāng)前最長(zhǎng)子串長(zhǎng)度
  current_len = 0
  for item in s[index:]:
  old_index = char_dict.get(item)
  if old_index is not None:
   index = old_index + 1
   char_dict.clear()
   break
  char_dict[item] = index
  index += 1
  current_len += 1
  if current_len > max_len:
  max_len = current_len
 return max_len

開始只是想跑通，沒想到超出了時(shí)間限制?？雌饋?lái)代碼顯得是有點(diǎn)啰嗦，但是思路應(yīng)該是沒有問題的，我們還是從遍歷的角度來(lái)優(yōu)化。

優(yōu)化：

在上面的代碼中，當(dāng)遇到重復(fù)字符時(shí)，遍歷的起始點(diǎn)就往后挪一位，但其實(shí)兩個(gè)重復(fù)字符之間的部分是不會(huì)重復(fù)的，比如字符串fbacdadfeed，在第一次從 f 開始遍歷遇到重復(fù)字符即第二個(gè) a 的時(shí)候，下一次遍歷不應(yīng)該從 b 開始，而是應(yīng)該從前一個(gè)重復(fù)字符的后一個(gè)字符即 c 開始。

確定思想，并多次優(yōu)化后的代碼如下：

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    char_dict = {}
    start, end, max_len = -1, 0, 0
    str_len = s.__len__()
    while end < str_len:
      char = s[end]
      if char in char_dict:
        old_index = char_dict[char]
        if old_index > start:
         start = old_index 
      diff = end -start
      if diff > max_len:
        max_len = diff 
      char_dict[char] = end
      end += 1
    return max_len;

這里使用了內(nèi)置的.__len__()方法來(lái)獲取字符串長(zhǎng)度而不是len()，并且使用了多個(gè)看似多此一舉的臨時(shí)變量來(lái)存儲(chǔ)值，比如char和diff，都是為了節(jié)省時(shí)間，蚊子小也是肉嘛。

結(jié)果也是 ok 的：