• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1163.按字典序排在最后的子串|LastSubstringinLexicographicalOrder ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(www.zengqiang.org
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Example 1:

Input: 

Example 2:

Input: 

Note:

  1. 1 <= s.length <= 10^5
  2. s contains only lowercase English letters.

给你一个字符串 s,找出它的所有子串并按字典序排列,返回排在最后的那个子串。

示例 1:

输入:"abab"
输出:"bab"
解释:我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。

示例 2:

输入:"leetcode"
输出:"tcode"

提示:

  1. 1 <= s.length <= 10^5
  2. s 仅含有小写英文字符。

 Runtime: 168 ms

Memory Usage: 22.9 MB
 1 class Solution {
 2     func lastSubstring(_ s: String) -> String {
 3         let arrS:[Character] = Array(s)
 4         var i:Int = 0
 5         let len:Int = s.count
 6         for j in 1..<len
 7         {
 8             var sz:Int = 0
 9             while(j + sz < len)
10             {
11                 if arrS[i + sz] == arrS[j + sz]
12                 {
13                     sz += 1
14                     continue
15                 }
16                 i = arrS[j + sz] > arrS[i + sz] ? j : i
17                 break                
18             }
19             if j + sz == len
20             {
21                 break
22             }
23         }        
24         return s.subString(i)
25     }
26 }
27 
28 extension String {
29     // 截取字符串:从index到结束处
30     // - Parameter index: 开始索引
31     // - Returns: 子字符串
32     func subString(_ index: Int) -> String {
33         let theIndex = self.index(self.endIndex, offsetBy: index - self.count)
34         return String(self[theIndex..<endIndex])
35     }    
36 }

224ms 
 1 class Solution {
 2     func lastSubstring(_ s: String) -> String {
 3                 
 4         let chars = Array(s)
 5         var highest: Character = "A"
 6         var idxs = [Int]()
 7         var distinct = 0
 8         for i in chars.indices {
 9             if chars[i] > highest {
10                 highest = chars[i]
11                 idxs = [Int]()
12                 distinct += 1
13             }
14 
15             if chars[i] == highest {
16                 idxs.append(i)
17             } else {
18                 distinct += 1
19             }
20         }
21 
22         if distinct == 1 {
23             return s
24         }
25 
26         var shift = 1;
27 
28         var nextLevel = [Int]()
29 
30         while idxs.count > 1 {
31             var shiftHighest: Character = "A"
32             for i in idxs {
33                 if i + shift < chars.count {
34                     if chars[i+shift] > shiftHighest {
35                         shiftHighest = chars[i+shift]
36                         nextLevel = [Int]()
37                     }
38                     if chars[i+shift] == shiftHighest {
39                         nextLevel.append(i)
40                     }
41                 }
42             }
43             idxs = nextLevel
44             nextLevel.removeAll()
45             shift += 1
46         }
47         return String(chars[idxs[0]..<chars.count])
48     }
49 }

476ms

 1 class Solution {
 2     func lastSubstring(_ s: String) -> String {
 3         
 4         var ret = s[s.startIndex...]
 5         
 6         for i in s.indices.dropFirst() {
 7             ret = max(ret, s[i...])
 8         }
 9         
10         return String(ret)
11     }
12 }

1772ms

 1 class Solution {
 2     func lastSubstring(_ s: String) -> String {
 3         var maxCharacter = Character(Unicode.Scalar(0))
 4         var maxIndex = 0
 5         
 6         for (index, character) in s.enumerated() {
 7             if character > maxCharacter {
 8                 maxCharacter = character
 9                 maxIndex = index
10             }
11             else if character == maxCharacter, 
12             String(s[String.Index(encodedOffset: index)...]) > String(s[String.Index(encodedOffset: maxIndex)...]) {
13                 maxCharacter = character
14                 maxIndex = index
15             }
16         }
17         
18         return String(s[String.Index(encodedOffset: maxIndex)...])
19     }
20 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap