[Swift]LeetCode1178. 猜字谜 | Number of Valid Words for Each Puzzle - Swift 教程-OStack程序员社区-中国程序员成长平台

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

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

word contains the first letter of puzzle.
For each letter in word, that letter is in puzzle.
For example, if the puzzle is "abcdefg", then valid words are "faced", "cabbage", and "baggage"; while invalid words are "beefed" (doesn\'t include "a") and "based" (includes "s" which isn\'t in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].

Example :

Input: 
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There\'re no valid words for "gaswxyz" cause none of the words in the list contains letter \'g\'.

Constraints:

1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] are English lowercase letters.
Each puzzles[i] doesn\'t contain repeated characters.

外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。

字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：

单词 word 中包含谜面 puzzle 的第一个字母。
单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 没有出现在谜面中）。

返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。

示例：

输入：
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
输出：[1,1,3,2,4,0]
解释：
1 个单词可以作为 "aboveyz" 的谜底 : "aaaa" 
1 个单词可以作为 "abrodyz" 的谜底 : "aaaa"
3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able"
2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas"
4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access"
没有单词可以作为 "gaswxyz" 的谜底，因为列表中的单词都不含字母 \'g\'。

提示：

1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] 都是小写英文字母。
每个 puzzles[i] 所包含的字符都不重复。

Runtime: 656 ms

Memory Usage: 36.7 MB

 1 class Solution {
 2     func findNumOfValidWords(_ words: [String], _ puzzles: [String]) -> [Int] {
 3         var result:[Int] = [Int]()
 4         var wordSets:[Int:Int] = [Int:Int]()
 5         var puzzles = puzzles.map{Array($0).map{$0.ascii}}
 6         var words = words.map{Array($0).map{$0.ascii - 97}}
 7         // Encode word of 26 chars in 31 bit (signed Int)
 8         for i in 0..<words.count
 9         {
10             var bits:Int = 0
11             for j in 0..<words[i].count
12             {
13                 bits |= 1 << words[i][j]
14             }
15             wordSets[bits,default:0] += 1
16         }
17 
18         for i in 0..<puzzles.count
19         {
20             var bits:Int = 0
21             var firstCharBitSet = 1 << (puzzles[i][0] - 97)
22             for j in 0..<puzzles[i].count
23             {
24                 bits |= 1 << (puzzles[i][j] - 97)
25             }
26             var count:Int = 0
27             var b:Int = bits
28             while(b > 0)
29             {
30                 if (b & firstCharBitSet) != 0 && wordSets[b] != nil
31                 {
32                     count += wordSets[b]!
33                 }
34                 b = --b & bits
35             }
36             result.append(count)
37         }
38         return result
39     }
40 }
41 
42 //Character扩展 
43 extension Character  
44 {  
45   //Character转ASCII整数值(定义小写为整数值)
46    var ascii: Int {
47        get {
48            return Int(self.unicodeScalars.first?.value ?? 0)
49        }       
50     }
51 }
52     
53 /*扩展Int类，实现自增++、自减--运算符*/
54 extension Int{
55     //--前缀:先自减再执行表达示
56     static prefix func --(num:inout Int) -> Int {
57         //输入输出参数num
58         num -= 1
59         //返回减1后的数值
60         return num
61     }
62 }

1020ms

 1 class Solution {
 2     func findNumOfValidWords(_ words: [String], _ puzzles: [String]) -> [Int] {        
 3         let table = Array("abcdefghijklmnopqrstuvwxyz")
 4         var dic = [Character: Int](), i = 0
 5         for c in table {
 6             dic[c] = i
 7             i += 1
 8         }
 9         var ans = [Int]()
10         var freq = [Int](repeating: 0, count: 1<<26)
11         for w in words {
12             let cw = Array(w)
13             var mask = 0
14             for c in cw {
15                 mask |= 1<<dic[c]!
16             }
17             freq[mask] += 1
18         }
19         for p in puzzles {
20             let cp = Array(p)
21             var mask = 0
22             for c in cp {
23                 mask |= 1<<dic[c]!
24             }
25 
26             let first = dic[cp.first!]!
27             var sub = mask
28             var total = 0
29             while true {
30                 if sub >> first & 1 != 0 {
31                     total += freq[sub]
32                 }
33                 if sub == 0 {
34                     break
35                 }
36                 sub = (sub-1)&mask
37             }
38             ans.append(total)
39         }
40         return ans
41     }
42 }

1908ms

 1 class Solution {
 2     func findNumOfValidWords(_ words: [String], _ puzzles: [String]) -> [Int] {
 3         let trie = Trie()
 4         var result = [Int]()
 5         
 6         for word in words {
 7             trie.insert(String(Set(word).sorted()))
 8         }
 9         
10         for puzzle in puzzles {
11             let firstCharacter = puzzle[String.Index(encodedOffset: 0)]
12             let sortedPuzzle = String(puzzle.sorted())
13             
14             result.append(trie.search(sortedPuzzle, firstCharacter, false))
15         }
16         
17         return result
18     }
19 }
20 
21 class TrieNode {
22     var hash = [Character:TrieNode]()
23     var countOfWords = 0
24     
25     func search(_ word: String, _ firstChar: Character, _ firstSeen: Bool) -> Int {
26         var count = 0
27         
28         if firstSeen { 
29             count += countOfWords 
30         }
31         
32         for i in 0..<word.count {
33             let wordChar = word[String.Index(encodedOffset: i)]
34             
35             guard let childNode = hash[wordChar] else { continue }
36             
37             if wordChar == firstChar {
38                 count += childNode.search(word, firstChar, true)
39             } else {
40                 count += childNode.search(word, firstChar, firstSeen)
41             }
42             
43         }
44         
45         return count
46     }
47 }
48 
49 class Trie {
50     let root = TrieNode()
51     
52     init(_ words: [String] = []) {
53         words.forEach(insert)
54     }
55     
56     func search(_ word: String, _ firstChar: Character, _ firstSeen: Bool) -> Int {
57         return root.search(word, firstChar, firstSeen)
58     }
59     
60     func insert(_ word: String) {
61         var current = root
62         for character in word {
63             if let node = current.hash[character] {
64                 current = node
65             } else {
66                 current.hash[character] = TrieNode()
67                 current = current.hash[character]!
68             }
69         }
70         current.countOfWords += 1
71     }
72 }

客服电话

电子邮件

[Swift]LeetCode1178. 猜字谜 | Number of Valid Words for Each Puzzle

请发表评论

全部评论

上一篇：

下一篇：

关于我们

产品与服务

解决方案

139-2527-9053