Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // scala
- object Solution {
- import scala.collection.mutable._
- // store current iteration index of "word"
- class Node(var word: String, var index: Int)
- def numMatchingSubseq(s: String, words: Array[String]): Int = {
- // setup
- var ans = 0
- var heads = new Array[Buffer[Node]](26) // heads of word, because word is only lower letter case, heads have length = 26
- for (i <- 0 until 26) {
- heads(i) = new ArrayBuffer[Node]
- }
- // init
- for (word <- words) {
- heads(word(0) - 'a') += new Node(word, 0)
- }
- // iterate s and count subsequence
- for (sch <- s) {
- // get words with current index, which word(index) == 'sch'
- var oldNodes = heads(sch - 'a')
- // prepare new bucket for new node
- heads(sch - 'a') = new ArrayBuffer[Node]
- for (node <- oldNodes) {
- // increase index
- node.index += 1
- if (node.index == node.word.length) {
- // if pointer go to end of word, we have 1 subsequence
- ans += 1
- } else {
- // move to new location.
- heads(node.word(node.index) - 'a') += node
- }
- }
- oldNodes.clear()
- }
- return ans
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement