Algorithem_Depth-First Search
原创Algorithem_Depth-First Search
原创
3. Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
<!--more-->
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.解法一
这道题的题目刚开始仔细看，看下面的例子1和2，以为要找的是重复字符串的长度，再后来以为是不重复字符串的长度，最后才看明白，要找的是，最长的子字符串里不包含有重复字符的长度。
题目看懂之后，想到的解法是最直观的，从左到右开始遍历字符串，设定一个默认长度1，然后依次往后取，如果取到的元素和包含在前面的元素中，则停止取，获取前面已经取到的元素的长度，然后遍历下一个字符串。可以想成，从第一个字符开始，有一个框框，框框的长度的从0开始慢慢增加，如果要增加的元素包含在框框中，则停止增加，获取先有框框的长度；然后遍历下一个字符，框框继续从1开始。
比如：
Input: s = "abcabcbb"
[a, b, c, a, b, c, b, b]
遍历：
第一个字符 a开始
框框长度0，当前元素 a，不在框框数组中，加入到框框数组里，框框长度+1
框框长度1，当前元素 b，不在框框数组中，加入到框框数组里，框框长度+1
框框长度2，当前元素 c，不在框框数组中，加入到框框数组里，框框长度+1
框框长度3，当前元素 a，包在框框数组中，框框停止增加，获取当前框框长度；然后遍历下一个字符
第二个字符 b
框框长度0，当前元素 b，不在框框数组中，加入到框框数组里，框框长度+1
框框长度1，当前元素 c，不在框框数组中，加入到框框数组里，框框长度+1
框框长度2，当前元素 a，不在框框数组中，加入到框框数组里，框框长度+1
框框长度3，当前元素 b，包在框框数组中，框框停止增加，获取当前框框长度 和上次获取到的比较大小，保存最大的；然后遍历下一个字符
...
依次类推代码如下：
class Solution {
func lengthOfLongestSubstring(_ s: String) -> Int {
if s.length == 0 {
return 0
}
let charList = Array(s)
var maxLength = 1
var savedList:[Character] = []
for i in 0..<charList.count {
var subLength = 0
var nextE = false
while !nextE {
if i + subLength >= charList.count {
maxLength = max(maxLength, savedList.count)
break
}
if savedList.contains(charList[i+subLength]) {
// 说明重复了
maxLength = max(maxLength, savedList.count)
savedList = []
subLength = 0
nextE = true
}
else {
savedList.append(charList[i+subLength])
subLength += 1
nextE = false
}
}
}
return maxLength
}
}但这个效率有点低，嗯，是否可以优化一下
优化点：
- 获取到最长的元素之后，遍历到 count-maxLength 的元素的时候，其实就可以不用遍历了，因为从这个元素开始，最长也就是 maxLength 了。
- 获取到最长的元素之后，后续元素的遍历，框框的长度可以以 maxlength 为准，只考虑比maxlength大的情况。
1，添加判断后，执行时间比不加判断多了65ms，而内存大小一致；
2，如果后续直接已框框的长度为准的话，还要判断框框里面的元素是有重复，会更费时。
那到底要怎么优化呢？
解法二
解法二和解法一的不同在于，解法一遇到重复字符之后，就继续遍历下一个，并且把框置为0从头开始；而解法二是遇到重复字符之后，遍历移除框最左边的元素，直到没有和要添加的元素重复为止，然后继续框向后遍历
比如：
Input: s = "abcabcbb"
[a, b, c, a, b, c, b, b]
遍历：
定义left 和 right，right 表示当前遍历进度，left 表示框框长度，数组 list 存储遍历过的字符
right=0，开始
当前元素 a，不在list数组中，加入到list数组里，right 向后
当前元素 b，不在list数组中，加入到list数组里，right 向后
当前元素 c，不在list数组中，加入到list数组里，right 向后
当前元素 a，在list数组中，left+1，list 数组最左侧元素弹出，变为[b, c]，判断 list 不包含 a，添加 a，right向后
...
依次类推
注意下面这里的逻辑：
到list 中为[a, b, c]，下一个元素为 b 时，list 中包含b，所以 left+1，list 最左侧弹出，变为[b, c]，判断后还是包含 b，所以继续 left + 1，list 最左侧弹出，变为[c]，再判断，不包含 b，添加 b，right 向后这里的过程可参考Longest Substring Without Repeating Characters - Leetcode 3 - Python
代码如下：
class Solution {
func lengthOfLongestSubstring(_ s: String) -> Int {
if s.length == 0 {
return 0
}
let charList = Array(s)
var list: [Character] = []
var left: Int = 0
var maxLength: Int = 0
for right in 0..<charList.count {
let charItem = charList[right]
while list.contains(charItem) {
list.remove(at: 0)
left += 1
}
list.append(charItem)
maxLength = max(maxLength, right - left + 1)
}
return maxLength
}
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。