Just DFS + memoization
Scala\nobject Solution {\n  def minimumDistance(word: String): Int = {\n    if (word.length <= 2) return 0\n\n\n    import scala.collection.mutable.Map\n    val
```Scala\nobject Solution {\n  def minimumDistance(word: String): Int = {\n    if (word.length <= 2) return 0\n\n\n    import scala.collection.mutable.Map\n    val map = Map[Char, Tuple2[Int, Int]]()\n    for (i <- 0 to 3; j <- 0 to 5) map.put((\'A\' + (i * 6) + j).toChar, (i, j))\n    map.put(\'Y\', (4, 0))\n    map.put(\'Z\', (4, 1))\n\n\n    def cost(from: Char, to: Char): Int = {\n      if (from == \' \') return 0\n      val t1 = map(from)\n      val t2 = map(to)\n      Math.abs(t1._1 - t2._1) + Math.abs(t1._2 - t2._2)\n    }\n\n\n    val len = word.length\n    val cache = Map[String, Int]()\n\n    def f(index: Int, currA: Char, currB: Char): Int = {\n      if (index == len) return 0\n      val key = index.toString + currA.toString + currB.toString\n      if (cache.contains(key)) return cache(key)\n      val targetChar = word.charAt(index)\n      val r = Math.min(\n        cost(currA, targetChar) + f(index + 1, targetChar, currB),\n        cost(currB, targetChar) + f(index + 1, currA, targetChar)\n      )\n      cache.put(key, r)\n      r\n    }\n    f(0, \' \', \' \')\n  }\n}\n```
[]