[Swift]LeetCode3. 无重复字符的最长子串 | Longest Substring W

发布时间：2020-12-14 05:10:45 所属栏目：百科来源：网络整理

导读：Given a string,find the length of the?longest substring?without repeating characters. Examples: Given? "abcabcbb" ,the answer is? "abc" ,which the length is 3. Given? "bbbbb" ,the answer is? "b" ,with the length of 1. Given? "pwwkew" ,the

Given a string,find the length of the?longest substring?without repeating characters.

Examples:

Given?"abcabcbb",the answer is?"abc",which the length is 3.

Given?"bbbbb",the answer is?"b",with the length of 1.

Given?"pwwkew",the answer is?"wke",with the length of 3. Note that the answer must be a?substring,?"pwke"?is a?subsequence?and not a substring.

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例?1:

输入: "abcabcbb"
输出: 3 
解释: 无重复字符的最长子串是 长度为 3。
"abc"，其

示例 2:

输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 ，其长度为 1。
"b"

示例 3:

输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是?，其长度为 3。
?    请注意，答案必须是一个子串，?是一个子序列 而不是子串。"wke""pwke"

36ms

 1 class Solution {
 2     func lengthOfLongestSubstring(_ s: String) -> Int {
 3         var m:[Int] = [Int](repeating: -1,count: 256)
 4         var res:Int = 0,left:Int = -1
 5         for i in 0..<s.count
 6         {
 7             let num:Int = s[s.index(s.startIndex,offsetBy: i)].toInt()
 8             left = max(left,m[num])
 9             m[num] = i
10             res = max(res,i - left)
11         }
12         return res
13     }
14 }
15 //Character扩展方法  
16 extension Character  
17 {  
18     func toInt() -> Int  
19     {  
20         var num:Int = Int()
21         for scalar in String(self).unicodeScalars  
22         {  
23             num = Int(scalar.value)  
24         }  
25         return num  
26     }  
27 }

20ms

 1 class Solution {
 2  func lengthOfLongestSubstring(_ s: String) -> Int {
 3      var right = 1
 4      var left = 0
 5      var i = 0
 6      var result = 0
 7      
 8      if s.count > 0 {
 9          result = right - left
10          let chars = Array(s.utf8)
11          
12          //Interate in a incremental window 
13          while right < chars.count {
14              i = left
15                 while i < right {
16                     //Check if a duplicate is found
17                     if chars[i] == chars[right] {
18                         left = i + 1
19                         break
20                     } 
21                 i = i + 1
22              }
23          result = max(result,right-left+1)     
24          right = right + 1
25      }
26      }
27      return result
28      }
29 }

28ms

 1 class Solution {
 2  func lengthOfLongestSubstring(_ s: String) -> Int {
 3         if s.characters.count == 0 {
 4             return 0
 5         }
 6         
 7         let chars = Array(s.utf8)
 8         var left = 0
 9         var right = 1
10         var result = right - left
11         var i = 0
12         
13         while right < chars.count {
14             i = left
15             while i < right {
16                 if chars[i] == chars[right] {
17                     left = i + 1
18                     break
19                 }
20                 i += 1
21             }
22             result = max(result,right - left + 1)
23             right += 1
24         }
25         
26         return result
27     }
28  }

36ms

 1 class Solution {
 2     func lengthOfLongestSubstring(_ s: String) -> Int {
 3         var arr = [Int](repeating: -1,count: 256)
 4         var s = Array(s)
 5         var currentLength = 0
 6         var maxLength = 0
 7         for i in 0..<s.count {
 8             let cValue = Int(s[i].unicodeScalars.first!.value)
 9             let preIndex = arr[cValue]
10             if arr[cValue] == -1 || i - preIndex > currentLength {
11                 currentLength += 1
12             } else {
13                 maxLength = max(currentLength,maxLength)
14                 currentLength = i - preIndex
15             }
16             arr[cValue] = i
17         }
18         
19         maxLength = max(currentLength,maxLength)
20         return maxLength
21     }
22 }

44ms

 1 class Solution {
 2     func lengthOfLongestSubstring(_ s: String) -> Int {
 3         
 4         var last:[Int] = Array.init(repeating: -1,count: 127)
 5         var start: Int = 0 // 起始位置
 6         var maxLength: Int = 0  // 最大长度
 7         
 8         let chars: [Int8]? = s.cString(using: String.Encoding.utf8)
 9         
10         for i in 0..<s.count {
11             
12             let hash_i: Int = Int(chars![i])
13             let hash_null: Int = 0
14             
15             if (last[hash_i - hash_null] >= start) {
16                 maxLength = max(maxLength,i-start)
17                 start = last[hash_i - hash_null] + 1
18             }
19             last[hash_i - hash_null] = i
20         }
21         maxLength = max(maxLength,s.count - start)
22         return maxLength
23     }
24 }

52ms

 1 class Solution {
 2     func lengthOfLongestSubstring(_ s: String) -> Int {
 3         let charArr = Array(s)
 4         let len = s.count
 5         var ans = 0
 6         var index = Array.init(repeating: 0,count: 128)
 7         var j = 0
 8         for i in 0..<len {
 9             let char = charArr[i]
10             if let v = char.unicodeScalars.first?.value {
11                 j = max(index[Int(v)],j)
12                 ans = max(ans,i - j + 1)
13                 index[Int(v)] = i + 1
14             }
15         }
16         return ans
17     }
18 }

84ms

 1 class Solution {
 2     func lengthOfLongestSubstring(_ s: String) -> Int {
 3         let cs = s.cString(using: .utf8)
 4         guard var chars = cs else { return 0 }
 5         guard chars.count > 1 else {
 6             return 0
 7         }
 8         chars.removeLast()
 9         var maxCount: Int = 0
10         var i = 0,j = 0
11         var map: [Int8: Int] = [:]
12         while j < chars.count {
13             if map.keys.contains(chars[j]) {
14                 i = max(map[chars[j]] ?? 0,i)
15             }
16             maxCount = max(maxCount,j - i + 1)
17             map[chars[j]] = j + 1
18             j += 1
19         }
20         return maxCount
21     }
22 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!