Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Trie - lowercase

a guest Feb 13th, 2017 96 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. import Foundation
  2.  
  3. class TrieNode{
  4.  
  5.     var children: [Character:TrieNode] = [:]
  6.     var isFinal: Bool = false
  7.     var prefixCount: Int = 0
  8.  
  9.  
  10.     init() {
  11.  
  12.     }
  13.  
  14. ///// called from a PARENT
  15.     func createChildFor(_ character: Character) -> TrieNode {
  16.         let node = TrieNode()
  17.  
  18.         children[character] = node
  19.  
  20.         return node
  21.     }
  22.  
  23.     func getOrCreateChildFor(_ character: Character) -> TrieNode {
  24.         if let child = children[character] {
  25.             return child
  26.         } else {
  27.             return createChildFor(character)
  28.         }
  29.     }
  30. }
  31. ///////////
  32.  
  33. class Trie {
  34.     var root = TrieNode()
  35.  
  36.     func validate(characters: [Character]) -> Bool {
  37.         var alphabetString = "abcdefghijklmnopqrstuvxyz"
  38.         let alphabetSequence = Array(alphabetString.characters)
  39.  
  40.         return characters.reduce(true) { result, char in
  41.             return result && alphabetSequence.contains(char)
  42.         }
  43.     }
  44.  
  45.     func getNodeFor(_ characters: [Character]) -> TrieNode? {
  46.         var node: TrieNode? = root
  47.         for character in characters {
  48.             node = node?.children[character]
  49.         }
  50.         return node
  51.     }
  52.  
  53.     func insert(_ word: String){
  54.         insert(characters: Array(word.characters))
  55.     }
  56.  
  57.     func insert(characters: [Character]) {
  58.       guard validate(characters: characters) else {
  59.           return
  60.       }
  61.       var node = root
  62.       node.prefixCount += 1
  63.       for character in characters {
  64.           node = node.getOrCreateChildFor(character)
  65.           node.prefixCount += 1
  66.       }
  67.       node.isFinal = true //
  68.     }
  69.  
  70.  
  71.     func query(_ word: String) -> Bool {
  72.         return query(characters: Array(word.characters))
  73.     }
  74.  
  75.     func query(characters: [Character]) -> Bool {
  76.       guard validate(characters: characters) else {
  77.           return false
  78.       }
  79.  
  80.       let node = getNodeFor(characters)
  81.  
  82.       if node == nil {
  83.         return false
  84.       }
  85.       return node!.isFinal
  86.     }
  87.  
  88.     func remove(_ word: String){
  89.         remove(characters: Array(word.characters))
  90.     }
  91.  
  92.     func remove(characters: [Character]) {
  93.       guard validate(characters: characters) else {
  94.           return
  95.       }
  96.  
  97.       let charactersNodes = getNodeSequence(characters: characters)
  98.       if charactersNodes.count != characters.count + 1 {
  99.           return
  100.       }
  101.  
  102.       var parent = root
  103.  
  104.       for (char, node) in charactersNodes {
  105.           node.prefixCount -= 1
  106.  
  107.           if node.prefixCount == 0 && node !== root {
  108.               parent.children.removeValue(forKey: char)
  109.               break // we deleted the reference to an entire sequence of nodes
  110.               // swift will delete those nodes from memory
  111.           }
  112.           parent = node
  113.       }
  114.  
  115.       charactersNodes.last?.node.isFinal = false
  116.  
  117.     }
  118.  
  119.     func getNodeSequence(characters: [Character]) -> [(char: Character, node: TrieNode)] {
  120.       var node : TrieNode? = root
  121.       var nodes:[(Character,TrieNode)] = []
  122.  
  123.       let tup = (Character("@"),node!)
  124.       nodes.append(tup)
  125.  
  126.       for character in characters {
  127.         node = node?.children[character]
  128.         if node == nil {
  129.           return nodes
  130.         }
  131.         let tup = (character, node!)
  132.         nodes.append(tup)
  133.       }
  134.  
  135.       return nodes
  136.     }
  137.  
  138.     func wordsSamePrefix(_ word: String) -> Int {
  139.         return wordsSamePrefix(characters: Array(word.characters))
  140.     }
  141.  
  142.     func wordsSamePrefix(characters: [Character]) -> Int {
  143.       guard validate(characters: characters) else {
  144.           return 0
  145.       }
  146.  
  147.       let node = getNodeFor(characters)
  148.  
  149.       if node == nil {
  150.         return 0
  151.       }
  152.  
  153.       return node!.prefixCount
  154.     }
  155.  
  156.  
  157.     func removeWordsPrefix(_ word: String)  {
  158.        removeWordsPrefix(characters: Array(word.characters))
  159.     }
  160.  
  161.     func removeWordsPrefix(characters: [Character]) {
  162.       guard validate(characters: characters) else {
  163.           return
  164.       }
  165.  
  166.       let charactersNodes = getNodeSequence(characters: characters)
  167.  
  168.       if charactersNodes.count != characters.count + 1 {
  169.           return
  170.       }
  171.  
  172.       let decreasePrefix = charactersNodes.last!.node.prefixCount
  173.  
  174.       var parent = root
  175.  
  176.       for (char, node) in charactersNodes {
  177.           node.prefixCount -= decreasePrefix
  178.           if node.prefixCount == 0 && node !== root {
  179.               parent.children.removeValue(forKey: char)
  180.               break // we deleted the reference to an entire sequence of nodes
  181.                   // swift will delete those nodes from memory
  182.           }
  183.           parent = node
  184.       }
  185.   }
  186.  
  187.     func kthWord(atIndex index: Int, from node: TrieNode? = nil, characters: [Character] = []) -> String? {
  188.         let node = node ?? root
  189.  
  190.         if index >= self.uniqueWords() {
  191.           return nil
  192.         }
  193.  
  194.         var alphabetString = "abcdefghijklmnopqrstuvxyz"
  195.         let alphabetSequence = Array(alphabetString.characters)
  196.  
  197.         if index == 0 && node.isFinal {
  198.             return String(characters)
  199.         }
  200.  
  201.         var skipped = 0
  202.         if node.isFinal {
  203.           skipped += 1
  204.         }
  205.  
  206.         for char in alphabetSequence {
  207.             if let child = node.children[char] {
  208.                 if skipped + child.prefixCount >  index {
  209.                     // find the word in the current child
  210.                     return kthWord(atIndex: index - skipped, from: child, characters: characters + [char])
  211.                 } else {
  212.                     // skip words from the current child
  213.                     skipped += child.prefixCount
  214.                 }
  215.             }
  216.  
  217.         }
  218.  
  219.         return nil
  220.     }
  221.  
  222.  
  223.     func uniqueWords() -> Int {
  224.       return root.prefixCount
  225.     }
  226.   }
  227.  
  228.  
  229.  
  230.   let myTrie = Trie()
  231.  
  232.   myTrie.insert("to");
  233.   myTrie.insert("tour");
  234.   myTrie.insert("tea");
  235.   myTrie.insert("roll");
  236.   myTrie.insert("round");
  237.  
  238.   let word = myTrie.kthWord(atIndex:2)
  239.   print(word!)   // optional "tea"
  240.  
  241.   print (myTrie.query("roll"))  //true
  242.   myTrie.remove("roll")
  243.   print (myTrie.query("roll"))  //false
  244.  
  245.   myTrie.removeWordsPrefix("r")
  246.   print (myTrie.query("round"))  //false
  247.  
  248.   print(myTrie.wordsSamePrefix("t")) //3
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top