[Swift]LeetCode1032.字符流|StreamofCharacters

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

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

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

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

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

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

Implement the StreamChecker class as follows:

StreamChecker(words): Constructor, init the data structure with the given words.
query(letter): returns true if and only if for some k >= 1, the last k characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.

Example:

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // init the dictionary.
streamChecker.query('a');          // return false
streamChecker.query('b');          // return false
streamChecker.query('c');          // return false
streamChecker.query('d');          // return true, because 'cd' is in the wordlist
streamChecker.query('e');          // return false
streamChecker.query('f');          // return true, because 'f' is in the wordlist
streamChecker.query('g');          // return false
streamChecker.query('h');          // return false
streamChecker.query('i');          // return false
streamChecker.query('j');          // return false
streamChecker.query('k');          // return false
streamChecker.query('l');          // return true, because 'kl' is in the wordlist

Note:

1 <= words.length <= 2000
1 <= words[i].length <= 2000
Words will only consist of lowercase English letters.
Queries will only consist of lowercase English letters.
The number of queries is at most 40000.

按下述要求实现 StreamChecker 类：

StreamChecker(words)：构造函数，用给定的字词初始化数据结构。
query(letter)：如果存在某些 k >= 1，可以用查询的最后 k个字符（按从旧到新顺序，包括刚刚查询的字母）拼写出给定字词表中的某一字词时，返回 true。否则，返回 false。

示例：

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // 初始化字典
streamChecker.query('a');          // 返回 false
streamChecker.query('b');          // 返回 false
streamChecker.query('c');          // 返回 false
streamChecker.query('d');          // 返回 true，因为 'cd' 在字词表中
streamChecker.query('e');          // 返回 false
streamChecker.query('f');          // 返回 true，因为 'f' 在字词表中
streamChecker.query('g');          // 返回 false
streamChecker.query('h');          // 返回 false
streamChecker.query('i');          // 返回 false
streamChecker.query('j');          // 返回 false
streamChecker.query('k');          // 返回 false
streamChecker.query('l');          // 返回 true，因为 'kl' 在字词表中。

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 2000
字词只包含小写英文字母。
待查项只包含小写英文字母。
待查项最多 40000 个。

2156ms

  1 let alphaMap: [Character: Int] = [
  2     "a": 0,
  3     "b": 1,
  4     "c": 2,
  5     "d": 3,
  6     "e": 4,
  7     "f": 5,
  8     "g": 6,
  9     "h": 7,
 10     "i": 8,
 11     "j": 9,
 12     "k": 10,
 13     "l": 11,
 14     "m": 12,
 15     "n": 13,
 16     "o": 14,
 17     "p": 15,
 18     "q": 16,
 19     "r": 17,
 20     "s": 18,
 21     "t": 19,
 22     "u": 20,
 23     "v": 21,
 24     "w": 22,
 25     "x": 23,
 26     "y": 24,
 27     "z": 25
 28 ]
 29 
 30 class Node {
 31     var val: Character
 32     var next: Node?
 33     var prev: Node?
 34 
 35     init(_ val: Character) {
 36         self.val = val
 37     }
 38 }
 39 
 40 
 41 class LinkedList {
 42     private(set) var head = Node(".")
 43     private(set) var tail = Node(".")
 44 
 45     init() {
 46         head.next = tail
 47         tail.prev = head
 48     }
 49 
 50     func add(node: Node) {
 51         node.next = head.next
 52         node.prev = head
 53         head.next?.prev = node
 54         head.next = node
 55     }
 56 
 57     func removeLast() {
 58         tail.prev?.prev?.next = tail
 59         tail.prev = tail.prev?.prev
 60     }
 61     
 62     func snapshot() {
 63         var node = head.next
 64         var str = ""
 65         while let n = node,
 66             n !== tail {
 67                 str += "\(n.val)"
 68                 node = n.next
 69                 if node !== tail {
 70                     str += " -> "
 71                 }
 72         }
 73     }
 74 }
 75 
 76 class Trie {
 77     private(set) var nodes: [Trie?] = [nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil]
 78     var isEnd = false
 79     
 80     func add(character: Character) -> Trie? {
 81         let index = alphaMap[character]!
 82         if nodes[index] == nil {
 83             nodes[index] = Trie()
 84         }
 85         return nodes[index]
 86     }
 87     
 88     func find(character: Character) -> Trie? {
 89         let index = alphaMap[character]!
 90         return nodes[index]
 91     }
 92 }
 93 
 94 class StreamChecker {
 95 
 96     private var trie = Trie()
 97     private var buffer = LinkedList()
 98     private var bufferCount = 0
 99     private var maxCount = 0
100 
101     init(_ words: [String]) {
102         for word in words {
103             var currentTrie: Trie? = trie
104             var count = 0
105             for char in word.reversed() {
106                 currentTrie = currentTrie?.add(character: char)
107                 count += 1
108             }
109             maxCount = max(maxCount, count)
110             currentTrie?.isEnd = true
111         }
112     }
113 
114     func query(_ letter: Character) -> Bool {
115         buffer.add(node: Node(letter))
116         bufferCount += 1
117         if bufferCount > maxCount {
118             bufferCount -= 1
119             buffer.removeLast()
120         }
121         var node = buffer.head.next
122         var currentTrie: Trie? = trie
123         while let n = node, n !== buffer.tail, let trie = currentTrie {
124             currentTrie = trie.find(character: n.val)
125             if currentTrie?.isEnd ?? false { return true }
126             node = n.next
127         }
128         return false
129     }
130 }

Runtime: 2240 ms

Memory Usage: 32.3 MB

 1 class StreamChecker {
 2     var root:TrieNode?
 3     var stream:[Int]
 4     init(_ words: [String]) {
 5         stream = [Int]()
 6         root = TrieNode()
 7         for word in words
 8         {
 9             var arrWord:[Int] = Array(word).map{$0.ascii - 97}
10             var m:Int = word.count
11             var cur:TrieNode? = root
12             for i in stride(from:m - 1,through:0,by:-1)
13             {
14                 if cur?.children[arrWord[i]] == nil
15                 {
16                     cur?.children[arrWord[i]] = TrieNode()
17                 }
18                 cur = cur?.children[arrWord[i]]
19             }            
20             cur?.is_word = true;
21         }        
22     }
23     
24     func query(_ letter: Character) -> Bool {
25         stream.append(letter.ascii)
26         var m:Int = stream.count
27         var cur:TrieNode? = root
28         for i in stride(from:m - 1,through:0,by:-1)
29         {
30             cur = cur?.children[stream[i] - 97]
31             if cur == nil {return false}
32             else if cur!.is_word {return true}
33         }
34         return false
35     }
36 }
37 
38 class TrieNode{
39     var is_word:Bool
40     var children:[TrieNode?]
41     init()
42     {
43         is_word = false
44         children = [TrieNode?](repeating:nil,count:26)
45     }
46 }
47 
48 //Character扩展 
49 extension Character  
50 {  
51   //Character转ASCII整数值(定义小写为整数值)
52    var ascii: Int {
53        get {
54            return Int(self.unicodeScalars.first?.value ?? 0)
55        }       
56     }
57 }
58 
59 /**
60  * Your StreamChecker object will be instantiated and called as such:
61  * let obj = StreamChecker(words)
62  * let ret_1: Bool = obj.query(letter)
63  */