前言
我们社区从本期开始会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。))的 Swift 算法题题解整理为文字版以方便大家学习与阅读。
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。
1. 描述
给定一个字符串 s
, 找出最长未重复的子字符串的长度.
2. 示例
示例 1
输入: s = "abcabcbb"
输出: 3
解释: 最长为重复的子字符串答案是 "abc", 长度为 3.
示例 2
输入: s = "bbb"
输出: 1
解释: 最长为重复的子字符串答案是 "b", 长度为 1.
示例 3
输入: s = "pww"
输出: 3
解释: 最长为重复的子字符串答案是 "wke", 长度为 3.
注意答案必须是自字符串,“pwke” 是一个子列,而不是一个自字符串.
示例 4
输入: s = ""
输出: 0
3. 答案
class LongestSubstring {
func lengthOfLongestSubstring(_ s: String) -> Int {
var maxLen = 0, startIdx = 0, charToPos = [Character: Int]()
let sChars = Array(s)
for (i, char) in sChars.enumerated() {
if let pos = charToPos[char] {
startIdx = max(startIdx, pos)
}
// update to next valid position
charToPos[char] = i + 1
maxLen = max(maxLen, i - startIdx + 1)
}
return maxLen
}
}
- 主要思想:使用字典存储非重复子字符串的下一个可能有效字符的位置,然后迭代字符串更新 maxLen、dictionary 和遇到重复时的 startIdx .
- 时间复杂度: O(n)
- 空间复杂度: O(n)
点击前往 LeetCode 练习
该算法题解的 github 仓库地址是:https://github.com/soapyigu/LeetCode-Swift