Scala Functional Segment Tree
Just for fun... Segment tree and functional programming are not necessary in this problem.\nscala\nobject Solution {\n    def isTransformable(s: String, t: Stri
Just for fun... Segment tree and functional programming are not necessary in this problem.\n```scala\nobject Solution {\n    def isTransformable(s: String, t: String): Boolean = {\n        def get(data: Map[Int, Int])(i: Int, j: Int, k: Int, l: Int, r: Int): Int = {\n            if (j == k || l == r) Int.MaxValue\n            else if (l == j && r == k) data(i)\n            else {\n                val (m, il, ir) = ((j + k) / 2, 2 * i + 1, 2 * i + 2)\n                get(data)(il, j, m, m min l, m min r) min get(data)(ir, m, k, m max l, m max r)\n            }\n        }\n\n        def put(data: Map[Int,Int])(i: Int, j: Int, k: Int, t: Int, v: Int): Map[Int,Int] = {\n            if (j + 1 == k) data + (i -> v)\n            else {\n                val (m, il, ir) = ((j + k) / 2, 2 * i + 1, 2 * i + 2)\n                val newData = if (t < m) put(data)(il, j, m, t, v) else put(data)(ir, m, k, t, v)\n                newData + (i -> (newData(il) min newData(ir)))\n            }\n        }\n\n        val sWithInd = s.map(_ - \'0\').zipWithIndex\n        val segTree = sWithInd.foldLeft(Map[Int, Int]().withDefaultValue(Int.MaxValue)) {\n            case (tree, (x, i)) => put(tree)(0, 0, s.size, i, x)\n        }\n        val indices = sWithInd.groupBy(_._1).mapValues(_.map(_._2).toVector).toMap\n\n        t.map(_ - \'0\').iterator.scanLeft(segTree, indices, true) { case ((tree, ind, res), digit) =>\n            ind.get(digit) match {\n                case Some(i +: tail) if get(tree)(0, 0, s.size, 0, i) >= digit =>\n                    (put(tree)(0, 0, s.size, i, Int.MaxValue), ind + (digit -> tail), true)\n                case _ => (tree, ind, false)\n            }\n        }.forall(_._3)\n    }\n}\n```
['Tree']