Advertisement
Guest User

Grokking #206 2

a guest
Jan 19th, 2022
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 1.27 KB | None | 0 0
  1. // scala
  2. object Solution {
  3.  
  4.   import scala.collection.mutable._
  5.  
  6.  
  7.   // store current iteration index of "word"
  8.   class Node(var word: String, var index: Int)
  9.  
  10.   def numMatchingSubseq(s: String, words: Array[String]): Int = {
  11.    
  12.     // setup
  13.     var ans = 0
  14.    
  15.     var heads = new Array[Buffer[Node]](26) // heads of word, because word is only lower letter case, heads have length = 26
  16.     for (i <- 0 until 26) {
  17.       heads(i) = new ArrayBuffer[Node]
  18.     }
  19.    
  20.     // init
  21.     for (word <- words) {
  22.       heads(word(0) - 'a') += new Node(word, 0)
  23.     }
  24.    
  25.     // iterate s and count subsequence
  26.     for (sch <- s) {
  27.       // get words with current index, which word(index) == 'sch'
  28.       var oldNodes = heads(sch - 'a')
  29.       // prepare new bucket for new node
  30.       heads(sch - 'a') = new ArrayBuffer[Node]
  31.      
  32.       for (node <- oldNodes) {
  33.         // increase index
  34.         node.index += 1
  35.        
  36.         if (node.index == node.word.length) {
  37.           // if pointer go to end of word, we have 1 subsequence
  38.           ans += 1
  39.         } else {
  40.           // move to new location.
  41.           heads(node.word(node.index) - 'a') += node
  42.         }                
  43.       }
  44.      
  45.       oldNodes.clear()      
  46.     }
  47.    
  48.     return ans    
  49.   }
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement