[Swift]LeetCode809. 情感丰富的文字 | Expressive Words_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 ch

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: 1Explanation: 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].count10             // words[i] 不能为空或者长度不小于S11             if lenW == 0  || lenW >= lenS {12                 return 013             }14             var j = 0,k = 0,streched = false,arrW = Array(words[i])15             while j < lenS && k < lenW {16                 var startS = j17                 var startW = k18                 if arrS[j] == arrW[k] {19                     while j < lenS - 1 && arrS[j] == arrS[j+1] {20                         j += 121                     }22                     while k < lenW - 1 && arrW[k] == arrW[k+1] {23                         k += 124                     }25                     // 如果S分组后的字符串是由某个字符重复2次及以上组成，则认为是可扩展26                     if j - startS >= 2 {27                         streched = true28                     }29                     //如果不可扩展，对应位置的字符串必须相同30                     else if j - startS != k - startW {31                         streched = false32                         break33                     }34                 }35                 else {36                     streched = false37                     break38                 }39                 j += 140                 k += 141             }42             if streched {43                 res += 144             }            45         }46         return res47     }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 = 011             while index < sRLE.count {12                 guard sRLE[index].0 == wRLE[index].0 else {13                     break14                 }15                 if !((sRLE[index].1 >= 3 && sRLE[index].1 >= wRLE[index].1) || sRLE[index].1 == wRLE[index].1) {16                     break17                 }18                 index += 119             }20             if index == sRLE.count {21                 result += 122             }23         }24         return result25     }26     27     private func getRLE(_ chars: [Character]) -> [(Character,Int)] {28         var start = 029         var pointer = 030         var result = [(Character,Int)]()31         while pointer < chars.count {32             while pointer < chars.count && chars[pointer] == chars[start] {33                 pointer += 134             }35             result.append((chars[start],pointer - start))36             start = pointer37         }38         return result39     }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 true20         }21         22         let set = Set(words)23         let sCompressed = compress(S)24         return words.filter{ isExpressive(sCompressed,compress($0)) }.count25     }    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 = 011             var j:Int = 012             while(i < m)13             {14                 if j < word.count && arrS[i] == arrWord[j]15                 {16                     j += 117                 }18                 else if i > 0 && arrS[i] == arrS[i - 1] && i + 1 < m && arrS[i] == arrS[i + 1]19                 {20                     i += 121                 }22                 else if !(i > 1 && arrS[i] == arrS[i - 1] && arrS[i] == arrS[i - 2])23                 {24                     break25                 }26                 i += 127             }28             if i == m && j == word.count29             {30                 res += 131             }32         }33         return res34     }35 }