[Swift]LeetCode809.情感丰富的文字|ExpressiveWords

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

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

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

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

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

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

Sometimes people repeat letters to represent extra feeling, such as "hello" -> "heeellooo", "hi" -> "hiiii". Here, we have groups, of adjacent letters that are all the same character, and adjacent characters to the group are different. A group is extended if that group is length 3 or more, so "e" and "o" would be extended in the first example, and "i" would be extended in the second example. As another example, the groups of "abbcccaaaa" would be "a", "bb", "ccc", and "aaaa"; and "ccc" and "aaaa" are the extended groups of that string.

For some given string S, a query word is stretchy if it can be made to be equal to S by extending some groups. Formally, we are allowed to repeatedly choose a group (as defined above) of characters c, and add some number of the same character c to it so that the length of the group is 3 or more. Note that we cannot extend a group of size one like "h" to a group of size two like "hh" - all extensions must leave the group extended - ie., at least 3 characters long.

Given a list of query words, return the number of words that are stretchy.

Example:
Input: 
S = "heeellooo"
words = ["hello", "hi", "helo"]
Output: 1
Explanation: 
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not extended.

Notes:

0 <= len(S) <= 100.
0 <= len(words) <= 100.
0 <= len(words[i]) <= 100.
S and all words in words consist only of lowercase letters

有时候人们会用额外的字母来表示额外的情感，比如 "hello" -> "heeellooo", "hi" -> "hiii"。我们将连续的相同的字母分组，并且相邻组的字母都不相同。我们将一个拥有三个或以上字母的组定义为扩张状态（extended），如第一个例子中的 "e" 和" o" 以及第二个例子中的 "i"。此外，"abbcccaaaa" 将有分组 "a" , "bb" , "ccc" , "dddd"；其中 "ccc" 和 "aaaa" 处于扩张状态。

对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，我们将这个单词定义为可扩张的（stretchy）。我们允许选择一个字母组（如包含字母 c ），然后往其中添加相同的字母 c 使其长度达到 3 或以上。注意，我们不能将一个只包含一个字母的字母组，如 "h"，扩张到一个包含两个字母的组，如 "hh"；所有的扩张必须使该字母组变成扩张状态（至少包含三个字母）。

输入一组单词，输出其中可扩张的单词数量。

示例：
输入： 
S = "heeellooo"
words = ["hello", "hi", "helo"]
输出：1
解释：
我们能通过扩张"hello"的"e"和"o"来得到"heeellooo"。
我们不能通过扩张"helo"来得到"heeellooo"因为"ll"不处于扩张状态。

说明：

0 <= len(S) <= 100。
0 <= len(words) <= 100。
0 <= len(words[i]) <= 100。
S 和所有在 words 中的单词都只由小写字母组成。

Runtime: 20 ms

Memory Usage: 19.6 MB

 1 class Solution {
 2     func expressiveWords(_ S: String, _ words: [String]) -> Int {
 3         let lenS = S.count
 4         if lenS == 0 { // S 不能为空
 5             return 0
 6         }
 7         var n = words.count, res = 0, arrS = Array(S)
 8         for i in 0..<n {
 9             let lenW = words[i].count
10             // words[i] 不能为空或者长度不小于S
11             if lenW == 0  || lenW >= lenS {
12                 return 0
13             }
14             var j = 0, k = 0, streched = false, arrW = Array(words[i])
15             while j < lenS && k < lenW {
16                 var startS = j
17                 var startW = k
18                 if arrS[j] == arrW[k] {
19                     while j < lenS - 1 && arrS[j] == arrS[j+1] {
20                         j += 1
21                     }
22                     while k < lenW - 1 && arrW[k] == arrW[k+1] {
23                         k += 1
24                     }
25                     // 如果S分组后的字符串是由某个字符重复2次及以上组成，则认为是可扩展
26                     if j - startS >= 2 {
27                         streched = true
28                     }
29                     //如果不可扩展，对应位置的字符串必须相同
30                     else if j - startS != k - startW {
31                         streched = false
32                         break
33                     }
34                 }
35                 else {
36                     streched = false
37                     break
38                 }
39                 j += 1
40                 k += 1
41             }
42             if streched {
43                 res += 1
44             }            
45         }
46         return res
47     }
48 }

28ms

 1 class Solution {
 2     func expressiveWords(_ S: String, _ words: [String]) -> Int {
 3         var sRLE = getRLE(Array(S))
 4         var result = 0
 5         for word in words {
 6             let wRLE = getRLE(Array(word))
 7             guard sRLE.count == wRLE.count else {
 8                 continue
 9             }
10             var index = 0
11             while index < sRLE.count {
12                 guard sRLE[index].0 == wRLE[index].0 else {
13                     break
14                 }
15                 if !((sRLE[index].1 >= 3 && sRLE[index].1 >= wRLE[index].1) || sRLE[index].1 == wRLE[index].1) {
16                     break
17                 }
18                 index += 1
19             }
20             if index == sRLE.count {
21                 result += 1
22             }
23         }
24         return result
25     }
26     
27     private func getRLE(_ chars: [Character]) -> [(Character, Int)] {
28         var start = 0
29         var pointer = 0
30         var result = [(Character, Int)]()
31         while pointer < chars.count {
32             while pointer < chars.count && chars[pointer] == chars[start] {
33                 pointer += 1
34             }
35             result.append((chars[start], pointer - start))
36             start = pointer
37         }
38         return result
39     }
40 }

40ms

 1 class Solution {
 2     func expressiveWords(_ S: String, _ words: [String]) -> Int {        
 3         func compress(_ s: String) -> [(Character, Int)] {
 4             return s.reduce(into: [(Character, Int)]()) {
 5                 if let (char, count) = $0.last, char == $1 {
 6                     $0[$0.count-1] = (char, count+1)
 7                 } else {
 8                     $0.append(($1, 1))
 9                 }
10             }
11         }
12         
13         func isExpressive(_ s: [(Character, Int)], _ t: [(Character, Int)]) -> Bool {
14             guard s.count == t.count else { return false }
15             for i in s.indices {
16                 if s[i] == t[i] { continue }
17                 if s[i].0 != t[i].0 || s[i].1 == 2 || s[i].1 < t[i].1 { return false }
18             }
19             return true
20         }
21         
22         let set = Set(words)
23         let sCompressed = compress(S)
24         return words.filter{ isExpressive(sCompressed, compress($0)) }.count
25     }    
26 }

Runtime: 44 ms

Memory Usage: 19.9 MB

 1 class Solution {
 2     func expressiveWords(_ S: String, _ words: [String]) -> Int {
 3         var arrS:[Character] = Array(S)        
 4         var res:Int = 0
 5         var m:Int = S.count
 6         var n:Int = words.count
 7         for word in words
 8         {
 9             var arrWord = Array(word)
10             var i:Int = 0
11             var j:Int = 0
12             while(i < m)
13             {
14                 if j < word.count && arrS[i] == arrWord[j]
15                 {
16                     j += 1
17                 }
18                 else if i > 0 && arrS[i] == arrS[i - 1] && i + 1 < m && arrS[i] == arrS[i + 1]
19                 {
20                     i += 1
21                 }
22                 else if !(i > 1 && arrS[i] == arrS[i - 1] && arrS[i] == arrS[i - 2])
23                 {
24                     break
25                 }
26                 i += 1
27             }
28             if i == m && j == word.count
29             {
30                 res += 1
31             }
32         }
33         return res
34     }
35 }