[Swift]LeetCode467.环绕字符串中唯一的子字符串|UniqueSubstringsinWraparoundString ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:

Input: "a"
Output: 1

Explanation: Only the substring "a" of string "a" is in the string s.

Example 2:

Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.

Example 3:

Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，所以 s 看起来是这样的："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

现在我们有了另一个字符串 p 。你需要的是找出 s 中有多少个唯一的 p的非空子串，尤其是当你的输入是字符串 p ，你需要输出字符串 s 中 p的不同的非空子串的数目。

注意: p 仅由小写的英文字母组成，p 的大小可能超过 10000。

示例 1:

输入: "a"
输出: 1
解释: 字符串 S 中只有一个"a"子字符。

示例 2:

输入: "cac"
输出: 2
解释: 字符串 S 中的字符串“cac”只有两个子串“a”、“c”。

示例 3:

输入: "zab"
输出: 6
解释: 在字符串 S 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。

8236ms

 1 class Solution {
 2     func findSubstringInWraproundString(_ p: String) -> Int {
 3         var cnt:[Int] = [Int](repeating:0,count:26)
 4         var res:Int = 0
 5         var len:Int = 0
 6         for i in 0..<p.count
 7         {
 8             var cur:Int = p[i].ascii - 97
 9             if i > 0 && p[i - 1].ascii != (cur + 26 - 1) % 26 + 97
10             {
11                 len = 0
12             }
13             len += 1
14             if len > cnt[cur]
15             {
16                 res += len - cnt[cur]
17                 cnt[cur] = len
18             }
19             
20         }
21         return res
22     }
23 }
24 
25 extension String {        
26     //subscript函数可以检索数组中的值
27     //直接按照索引方式截取指定索引的字符
28     subscript (_ i: Int) -> Character {
29         //读取字符
30         get {return self[index(startIndex, offsetBy: i)]}
31     }
32 }
33 
34 extension Character  
35 {  
36   //属性：ASCII整数值(定义小写为整数值)
37    var ascii: Int {
38         get {
39             let s = String(self).unicodeScalars
40             return Int(s[s.startIndex].value)
41         }
42     }
43 }

Memory Usage: 4194kb

 1 class Solution {
 2     func findSubstringInWraproundString(_ p: String) -> Int {
 3         var count: [Character: Int] = [ : ]
 4         let s = Array("abcdefghijklmnopqrstuvwxyz")
 5         let p = Array(p)
 6         for c in s {
 7             count[c] = 0
 8         }
 9         
10         var maxLen = 0
11         
12         for i in 0 ..< p.count {
13             if i > 0 && (p[i].unicodeScalars.first!.value == p[i - 1].unicodeScalars.first!.value + 1 || p[i - 1].unicodeScalars.first!.value == p[i].unicodeScalars.first!.value + 25) {
14                 maxLen += 1
15             } else {
16                 maxLen = 1
17             }
18             count[p[i]] = max(count[p[i]]!, maxLen)
19         }
20         
21         return count.values.reduce(0, { $0 + $1 })
22     }
23 }