ToB企服应用市场:ToB评测及商务社交产业平台

标题: LeetCode【0003】无重复字符的最宗子串 [打印本页]
作者: 乌市泽哥    时间: 2024-11-11 22:02
标题: LeetCode【0003】无重复字符的最宗子串
1 中文标题

给定一个字符串                                    s                              s                  s，请找出其中不含有重复字符的 最长 子串的长度。
示例 1：

示例 2：

示例 3：

提示：

2 求解思绪

2.1 基础解法： 暴力解法

思绪
具体求解思绪：

求解示例
  1. 输入: "abcabcbb"
  2. 第1轮(i=0):  # 外循环
  3.     # 内循环
  4.     - j=0: seen={'a'}, curr_len=1
  5.     - j=1: seen={'a','b'}, curr_len=2
  6.     - j=2: seen={'a','b','c'}, curr_len=3
  7.     - j=3: 遇到'a'重复，break, max_len=3
  9. 第2轮(i=1):
  10.     - j=1: seen={'b'}, curr_len=1
  11.     - j=2: seen={'b','c'}, curr_len=2
  12.     - j=3: seen={'b','c','a'}, curr_len=3
  13.     - j=4: 遇到'b'重复，break, max_len=3
  15. ... 依此类推
复制代码
Python代码
  1. class Solution:
  2.     def lengthOfLongestSubstring(self, s: str) -> int:
  3.         # 记录最长无重复子串的长度
  4.         max_len = 0
  5.         
  6.         # 遍历字符串的每个字符作为起始位置
  7.         for i in range(len(s)):
  8.             # 用集合记录当前子串中出现过的字符
  9.             seen = set()
  10.             # 记录当前子串的长度
  11.             curr_len = 0
  12.             
  13.             # 从起始位置向后遍历，直到找到重复字符或到达字符串末尾
  14.             for j in range(i, len(s)):
  15.                 # 如果当前字符已经在集合中，说明出现重复
  16.                 if s[j] in seen:
  17.                     break
  18.                
  19.                 # 将当前字符添加到集合中
  20.                 seen.add(s[j])
  21.                 # 当前子串长度加1
  22.                 curr_len += 1
  23.             
  24.             # 更新最长无重复子串的长度
  25.             max_len = max(max_len, curr_len)
  26.         
  27.         return max_len
复制代码
时空复杂度分析

2.2 优化解法： 动态规划解法

思绪
（1）动态规划状态

（2）状态转移方程
  1. if s[i] 未出现过:
  2.     dp[i] = dp[i-1] + 1
  3. else:
  4.     dp[i] = min(dp[i-1] + 1, i - last_pos[s[i]])
复制代码
示例
  1. 输入: "abcabcbb"
  2. 初始化：dp[0] = 1, last_pos['a'] = 0
  4. i=1: 'b'
  5. - 未出现过
  6. - dp[1] = dp[0] + 1 = 2
  7. - last_pos['b'] = 1
  9. i=2: 'c'
  10. - 未出现过
  11. - dp[2] = dp[1] + 1 = 3
  12. - last_pos['c'] = 2
  14. i=3: 'a'
  15. - 出现过，上次在位置0
  16. - dp[3] = min(dp[2] + 1, 3 - 0) = min(4, 3) = 3
  17. - last_pos['a'] = 3
  19. ... 依此类推
复制代码
python代码
  1. class Solution:
  2.     def lengthOfLongestSubstring(self, s: str) -> int:
  3.         # 处理空字符串情况
  4.         if not s:
  5.             return 0
  6.             
  7.         # dp[i]表示以s[i]结尾的最长无重复子串的长度
  8.         dp = [0] * len(s)
  9.         
  10.         # 记录每个字符最后一次出现的位置
  11.         last_pos = {}
  12.         
  13.         # 初始化第一个字符
  14.         dp[0] = 1
  15.         last_pos[s[0]] = 0
  16.         max_len = 1
  17.         
  18.         # 从第二个字符开始遍历
  19.         for i in range(1, len(s)):
  20.             # 当前字符之前没有出现过
  21.             if s[i] not in last_pos:
  22.                 # 直接在前一个状态的基础上加1
  23.                 dp[i] = dp[i-1] + 1
  24.             else:
  25.                 # 当前字符之前出现过，需要比较两个长度：
  26.                 # 1. 前一个状态的长度加1
  27.                 # 2. 当前位置与该字符上次出现位置的距离
  28.                 dp[i] = min(dp[i-1] + 1, i - last_pos[s[i]])
  29.             
  30.             # 更新字符最后出现的位置
  31.             last_pos[s[i]] = i
  32.             # 更新最大长度
  33.             max_len = max(max_len, dp[i])
  34.         
  35.         return max_len
复制代码
时空复杂度分析

总空间复杂度：                                   O                         (                         n                         +                         m                         i                         n                         (                         m                         ,                         n                         )                         )                         =                         O                         (                         n                         )                              O(n + min(m,n)) = O(n)                  O(n+min(m,n))=O(n)
算法优化

  1. class Solution:
  2.     def lengthOfLongestSubstring(self, s: str) -> int:
  3.         # 获取字符串长度
  4.         n = len(s)
  5.         
  6.         # 特殊情况处理
  7.         # 1. 空字符串或单个字符，直接返回长度
  8.         if n <= 1:
  9.             return n
  10.         # 2. 如果所有字符都不相同，直接返回字符串长度
  11.         if len(set(s)) == n:
  12.             return n
  13.             
  14.         # 使用数组代替哈希表记录字符最后出现的位置
  15.         # ASCII字符集大小为128，初始化为-1表示字符未出现过
  16.         last_pos = [-1] * 128
  17.         
  18.         # prev_len：记录以前一个字符结尾的最长无重复子串长度
  19.         prev_len = 1
  20.         # max_len：记录全局最长无重复子串长度
  21.         max_len = 1
  22.         
  23.         # 初始化第一个字符的位置
  24.         last_pos[ord(s[0])] = 0
  25.         
  26.         # 从第二个字符开始遍历
  27.         for i in range(1, n):
  28.             # 提前终止优化
  29.             # 如果剩余的字符长度加上当前长度小于已找到的最大长度
  30.             # 则不可能找到更长的无重复子串，可以直接结束
  31.             if max_len >= n - i + prev_len:
  32.                 break
  33.                
  34.             # 获取当前字符的ASCII码
  35.             char_idx = ord(s[i])
  36.             
  37.             # 计算当前以s[i]结尾的最长无重复子串长度
  38.             if last_pos[char_idx] == -1:
  39.                 # 情况1：当前字符从未出现过
  40.                 # 直接在前一个长度基础上加1
  41.                 curr_len = prev_len + 1
  42.             else:
  43.                 # 情况2：当前字符之前出现过
  44.                 # 需要比较两个长度：
  45.                 # a. 前一个长度加1
  46.                 # b. 当前位置与该字符上次出现位置的距离
  47.                 curr_len = min(prev_len + 1, i - last_pos[char_idx])
  48.             
  49.             # 更新字符最后出现的位置
  50.             last_pos[char_idx] = i
  51.             
  52.             # 更新全局最大长度
  53.             max_len = max(max_len, curr_len)
  54.             
  55.             # 更新前一个长度，用于下一轮计算
  56.             prev_len = curr_len
  57.             
  58.         return max_len
复制代码
2.3 最优解法：滑动窗口

思绪
（1）滑动窗口

（2）窗口滑动机制

示例
  1. 输入: "abcabcbb"
  2. 初始状态：left=0, right=0, window={}
  4. 1. 处理'a':
  5.    window={'a':0}, left=0, right=0, max_len=1
  7. 2. 处理'b':
  8.    window={'a':0, 'b':1}, left=0, right=1, max_len=2
  10. 3. 处理'c':
  11.    window={'a':0, 'b':1, 'c':2}, left=0, right=2, max_len=3
  13. 4. 处理'a':
  14.    发现重复，left更新为1
  15.    window={'a':3, 'b':1, 'c':2}, left=1, right=3, max_len=3
  17. ...依此类推
复制代码
python代码
  1. class Solution:
  2.     def lengthOfLongestSubstring(self, s: str) -> int:
  3.         # 用字典维护字符最后出现的位置
  4.         window = {}
  5.         # 记录最长无重复子串的长度
  6.         max_len = 0
  7.         # 滑动窗口的左边界
  8.         left = 0
  9.         
  10.         # 遍历字符串，right为滑动窗口的右边界
  11.         for right, char in enumerate(s):
  12.             # 如果当前字符已在窗口中，需要更新左边界
  13.             # 取max是为了确保left不会回退
  14.             if char in window:
  15.                 left = max(left, window[char] + 1)
  16.             
  17.             # 计算当前无重复子串的长度并更新最大长度
  18.             curr_len = right - left + 1
  19.             max_len = max(max_len, curr_len)
  20.             
  21.             # 更新字符最后出现的位置
  22.             window[char] = right
  23.         
  24.         return max_len
复制代码
时空复杂度分析

基于滑动窗口的方法实现简单，代码逻辑清楚，不像动态规划代码复杂，逻辑复杂
3 标题总结

标题难度：中等
数据布局： 哈希表、字符串
应用算法： 动态规划、滑动窗口

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4