LeetCode练习心得——#3. 最长不含重复字符的子字符串
5星
- 浏览量: 0
- 大小:None
- 文件类型：PDF
简介：
本篇文章记录了我在LeetCode上解决“最长不含重复字符的子字符串”问题的心得体会，分享了解题思路和优化过程。
难度：中等
题目描述：
LeetCode中的第3题是一个经典的字符串处理问题，名为“无重复字符的最长子串”。该问题要求找到给定字符串中最长的一个不含任何重复字符的子串。例如，对于输入字符串 pwwkew ，最大的不包含重复字符的子串是 wke, 长度为 3。
解题分析：
解决这个问题的有效方法之一就是使用滑动窗口策略和哈希表来追踪每个字符及其在该字符串中的最新位置。具体步骤如下：
1. 初始化一个空字典 `d` 来存储字符以及它们的索引。
2. 定义两个变量：`start` 用于记录当前子串的起始位置，初始值设为 -1；而 `max_len` 则用来跟踪最长无重复字符子串的长度，初始化为0。
3. 遍历输入字符串中的每个字符，使用索引 `i` 表示当前迭代的位置。
4. 对于每一个字符，检查它是否已经存在于字典中。如果存在且其对应的值大于 `start` ，这表明该字符是重复出现的，并需要更新 `start` 为这个重复字符上一次出现时的索引位置。
5. 如果当前处理到的字符不在字典里或者它的上次出现的位置小于等于 `start`, 则将该字符及其当前位置添加进字典中，以记录它最新的位置信息。
6. 在每次迭代结束的时候，计算从 `i - start` 得出当前子串长度，并与之前的最大值进行比较。如果当前子串更长，则更新最大值为新的长度。
7. 完成遍历后，返回 `max_len` 作为最长无重复字符子串的长度。
代码实现：
```python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
start = -1
max_len = 0
d = {}
for i in range(len(s)):
if s[i] in d and d[s[i]] > start:
start = d[s[i]]
d[s[i]] = i
if i - start > max_len:
max_len = i - start
return max_len
```
模拟笔试：
在实际的编程面试或笔试中，你可能需要提供完整的代码实现，包括输入输出部分。以下是一个示例：
```python
def main():
s = input() # 用户输入字符串，例如 pwwkew
solution = Solution()
output = solution.lengthOfLongestSubstring(s)
print(output) # 输出最长无重复字符子串的长度
if __name__ == __main__:
main()
```
此模拟笔试代码中，我们首先接收用户提供的输入字符串 `s` ，然后调用类 `Solution` 的方法计算最长不含重复字符子串的长度，并将该结果输出。
这道题目考察了对字符串处理、滑动窗口技术和哈希表应用的理解。通过使用字典来存储每个字符的位置信息，我们能够在 O(n) 时间复杂度内解决这个问题，其中 n 是输入字符串的长度。此外，这也锻炼了解决问题时的设计和优化能力。
全部评论 (0)
