[关闭]
@liweiwei1419 2019-05-24T00:37:28.000000Z 字数 2988 阅读 942

LeetCode 第 3 题:最长不重复字符串

动态规划 滑动窗口 散列表



传送门:3. 无重复字符的最长子串。这道题也是《剑指Offer》上第 48 题。

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

  1. 输入: "abcabcbb"
  2. 输出: 3
  3. 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3

示例 2:

  1. 输入: "bbbbb"
  2. 输出: 1
  3. 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1

示例 3:

  1. 输入: "pwwkew"
  2. 输出: 3
  3. 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3
  4. 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

解法1:哈希表 + 隔板法(好几种写法)

判断一个元素有没有出现过,使用哈希表是最自然的想法。

以下面的例子进行说明:

判断连续区间内是否出现重复元素,可以使用 set,又要存储位置,所以使用 dict

Python 代码1:(推荐写法)

LeetCode 第 3 题:无重复字符的最长子串-1

等价的写法:(我的练习)

  1. class Solution:
  2. def lengthOfLongestSubstring(self, s):
  3. """
  4. :type s: str
  5. :rtype: int
  6. """
  7. map = dict()
  8. max_len = 0
  9. # 可以认为是标定的起始
  10. pointer = 0
  11. for index, c in enumerate(s):
  12. if c in map:
  13. pointer = max(pointer, map[c] + 1)
  14. max_len = max(max_len, index - pointer + 1)
  15. # 每次遍历都更新当前遍历到的字母的位置
  16. map[c] = index
  17. return max_len
  18. if __name__ == '__main__':
  19. s = 'pwwkew'
  20. solution = Solution()
  21. result = solution.lengthOfLongestSubstring(s)
  22. print(result)

需要注意的一点是:只有重复出现的位置大于标定点的时候,才要更新,更新的位置是当前位置 + 1。即只要出现重复,隔板就向后移动一位,然后每一轮都计算当前与隔板的距离。

Python 代码2:(不如上面的代码语义清晰)

  1. class Solution:
  2. def lengthOfLongestSubstring(self, s):
  3. # 特判
  4. l = len(s)
  5. if l < 2:
  6. return l
  7. # 隔板法
  8. # key:字符,val 出现的索引
  9. map = dict()
  10. point = 0
  11. res = 1
  12. for i in range(l):
  13. # 关键1:map[s[i]] >= point,等于是可以的
  14. if s[i] in map and map[s[i]] >= point:
  15. # 先把隔板向后移动一位
  16. point = map[s[i]] + 1
  17. # 然后记录最长不重复子串的长度
  18. res = max(res, i - point + 1)
  19. # 关键2:无论如何都更新位置
  20. map[s[i]] = i
  21. return res

等价的写法:(我的练习)

  1. class Solution:
  2. def lengthOfLongestSubstring(self, s):
  3. """
  4. :type s: str
  5. :rtype: int
  6. """
  7. l = len(s)
  8. if l <= 1:
  9. return l
  10. point = 0
  11. map = dict()
  12. result = 0
  13. for index, alpha in enumerate(s):
  14. if alpha in map and map[alpha] >= point:
  15. point = map[alpha] + 1
  16. # 每次要做两件事:1、计算无重复子串长度
  17. result = max(result, index - point + 1)
  18. # 2、更新索引
  19. map[alpha] = index
  20. return result

解法2:动态规划

dp[i]:以 s[i] 结尾的最长不重复子串,这个状态的设置与最长上升子序列、最大连续子数组是一样的。

下面考虑 dp[i] 和 dp[i-1] 之间的关系。关键在于 dp [i-1] 与距离出现相同字符的时候,两个相同字符的距离的比较。

LeetCode 第 3 题:无重复字符的最长子串-2

LeetCode 第 3 题:无重复字符的最长子串-3

Python 代码:

  1. class Solution:
  2. def lengthOfLongestSubstring(self, s):
  3. """
  4. :type s: str
  5. :rtype: int
  6. """
  7. # 特判
  8. l = len(s)
  9. if l < 2:
  10. return l
  11. # dp[i] 表示以 s[i] 结尾的最长不重复子串的长度
  12. # 因为自己肯定是不重复子串,所以初始值设置为 1
  13. dp = [1 for _ in range(l)]
  14. map = dict()
  15. map[s[0]] = 0
  16. for i in range(1, l):
  17. if s[i] in map:
  18. if i - map[s[i]] > dp[i - 1]:
  19. dp[i] = dp[i - 1] + 1
  20. else:
  21. dp[i] = i - map[s[i]]
  22. else:
  23. dp[i] = dp[i - 1] + 1
  24. # 设置字符与索引键值对
  25. map[s[i]] = i
  26. # 最后拉通看一遍最大值
  27. return max(dp)

解法3:滑动窗口、双指针

Python 代码:推荐写法

  1. # 滑动窗口的做法
  2. class Solution:
  3. def lengthOfLongestSubstring(self, s):
  4. """
  5. :type s: str
  6. :rtype: int
  7. """
  8. # 特判
  9. size = len(s)
  10. if size < 2:
  11. return size
  12. l = 0
  13. r = -1
  14. counter = [0 for _ in range(256)]
  15. res = 1
  16. while l < size:
  17. # 尝试走一步,如果可以走,就计算
  18. if r + 1 < size and counter[ord(s[r + 1])] == 0:
  19. # 表示没有重复元素,r 可以加 1
  20. counter[ord(s[r + 1])] += 1
  21. r += 1
  22. else:
  23. # 有重复元素,左边就要减 1
  24. counter[ord(s[l])] -= 1
  25. l += 1
  26. res = max(res, r - l + 1)
  27. return res

Python 代码:滑动窗口写法2

  1. class Solution:
  2. def lengthOfLongestSubstring(self, s):
  3. """
  4. :type s: str
  5. :rtype: int
  6. """
  7. # 特判
  8. size = len(s)
  9. if size < 2:
  10. return size
  11. l = 0
  12. r = -1
  13. counter = [0 for _ in range(256)]
  14. res = 1
  15. while l < size:
  16. # 首先"右指针"不断向右边尝试,走到出现重复的最右边
  17. while r + 1 < size and counter[ord(s[r + 1])] == 0:
  18. # 表示没有重复元素,r 可以加 1
  19. counter[ord(s[r + 1])] += 1
  20. r += 1
  21. # 此时,记录不重复子串是"左指针"固定时候最长
  22. res = max(res, r - l + 1)
  23. # 考虑移动"左指针"
  24. # 此时 s[r+1] 就是已经扫过的区间里重复的元素,要把它剔除出去
  25. while r + 1 < size and s[l] != s[r + 1]:
  26. # 有重复元素,左边就要减 1
  27. counter[ord(s[l])] -= 1
  28. l += 1
  29. # 出了上一个循环以后,还要再把左指针向右移动一格,否则右指针不能向右移动
  30. counter[ord(s[l])] -= 1
  31. l += 1
  32. return res

(本节完)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注