[Swift]LeetCode1178. 맞춤법 | 각 퍼즐의 유효한 단어 수

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ 위챗 공중호: 감히 (WeiGanTechnologies)➤ 블로그원 주소: 산청영지(https://www.cnblogs.com/strengthen/) ➤ 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<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<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 }