Scala Solution, DO


  • 0
    A
    object Solution {
      def strangePrinter(s: String): Int = {
        if(s == "")
          return 0
        val mem = Array.fill(110, 110)(-1)
        val len = s.length();
        def dp(i: Int, j: Int): Int = {
          if(mem(i)(j) != -1) {
            return mem(i)(j)
          }
          if (i > j) return 0
          else {
            val b = dp(i+1, j) + 1
            /* split i to j by i+1+n */
            val l = List.tabulate (j-i) (n => dp(i, i+n) + dp(i+2+n, j))
            val table = List.tabulate (j-i) (n => s.apply(i) == s.apply(i+1+n))
            val zipped = l.zip(table)
            val filtered = zipped.filter { case (_, b) => b }
            val ll = filtered.map { case (a, _) => a}
            if (ll == Nil) {
              mem(i)(j) = b
              return b
            }
            val best = ll.reduce(math.min)
            mem(i)(j) = math.min(b, best)
            return math.min(b, best)
          }
        }
        return dp(0, len-1)
      }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.