PreFixMapSum

prefixmapsum.kt

package cracking.ch4

import org.junit.Test
import java.util.*

class PrefixMapSum {

    var trie = Trie(0)

    @Test
    fun test() {
        val pre = PrefixMapSum()
        pre.insert("columnar", 3)
        println(pre.sum("col"))
        pre.insert("column", 2)
        println(pre.sum("col"))
        println(pre.sum("columnar"))
    }

    fun insert(key: String, value: Int) {
        var tempTrie = trie

        for (letter in 0 until key.length) {
            val index = key[letter] - 'a'

            if (tempTrie.children[index] == null) {
                tempTrie.children[index] = Trie(value)
            } else {
                tempTrie.children[index]!!.sum += value
            }

            tempTrie = tempTrie.children[index]!!
        }
    }
  
    tailrec fun recur(tempTrie: Trie?, prefix: String) : Int {
            if (tempTrie == null || prefix.isEmpty()) return 0

            if (prefix.length == 1) {
                return tempTrie.sum
            }

            return recur(tempTrie.children[prefix[0] - 'a'], prefix.substring(1, prefix.length))
        }

    fun sum(prefix: String) : Int {
        val tempTrie = trie;
        return recur(tempTrie, prefix)
    }

}

data class Trie(var sum: Int, var children: Array<Trie?> = arrayOfNulls(26)) {
    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (javaClass != other?.javaClass) return false

        other as Trie

        if (sum != other.sum) return false
        if (!Arrays.equals(children, other.children)) return false

        return true
    }

    override fun hashCode(): Int {
        var result = sum
        result = 31 * result + Arrays.hashCode(children)
        return result
    }
}

tailrec - will rewrite recursion method in an while loop. The improvements come from the fact that method calls are more expensive than simply looping and reduces risk of stack overflow.

Decompiled Java:

   public final int recur(@Nullable Trie tempTrie, @NotNull String prefix) {
      while(true) {
         Intrinsics.checkParameterIsNotNull(prefix, "prefix");
         if (tempTrie != null) {
            CharSequence var3 = (CharSequence)prefix;
            if (var3.length() != 0) {
               if (prefix.length() == 1) {
                  return tempTrie.getSum();
               }

               Trie var10001 = tempTrie.getChildren()[prefix.charAt(0) - 97];
               byte var4 = 1;
               int var5 = prefix.length();
               Trie var7 = var10001;
               String var10000 = prefix.substring(var4, var5);
               Intrinsics.checkExpressionValueIsNotNull(var10000, "(this as java.lang.Strin…ing(startIndex, endIndex)");
               String var8 = var10000;
               prefix = var8;
               tempTrie = var7;
               continue;
            }
         }

         return 0;
      }
   }