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

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

导读：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?

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","dddd"；其中 "ccc" 和 "aaaa" 处于扩张状态。

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

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

示例：
输入： 
S = "heeellooo"
words = ["hello","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 }

（编辑：李大同）

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