Palindromic Decomposition

PalindromicDecomposition.scala

/**
 * Compute all palindromic decompositions of a string
 *
 * O(n²) time and space
 */
trait PalindromicDecomposition {
  type Intervals = Vector[(Int, Int)]

  def decompose(s: String): Seq[String] = {
    val memo = Array.ofDim[Vector[Intervals]](s.length)

    def isPalindrome(i: Int, j: Int): Boolean =
      if (i >= j) true
      else if (s(i) != s(j)) false
      else isPalindrome(i + 1, j - 1)

    def decomp(i: Int = 0): Vector[Intervals] = {
      if (memo(i) != null) memo(i)
      else {
        var result = Vector.empty[Intervals]

        i until s.length foreach { j =>
          if (isPalindrome(i, j)) {
            if (j == s.length - 1) {
              result :+= Vector((i, j))
            } else {
              result ++= decomp(j + 1) map (suffix => Vector((i, j)) ++ suffix)
            }
          }
        }
        memo(i) = result
        result
      }
    }

    def intervalsToString(intervals: Intervals): String =
      intervals.foldLeft("")((acc, elem) => acc + s.substring(elem._1, elem._2 + 1) + "|")

    decomp() map intervalsToString
  }
}

PalindromicDecompositionTest.scala

import org.scalatest.FunSuite

class PalindromicDecompositionTest extends FunSuite with PalindromicDecomposition {

  def run(s: String, expected: Set[String]): Unit = {
    val seq = decompose(s)
    seq foreach println
    val set = Set.empty[String] ++ seq
    println(seq.size, set.size)
    assert(seq.size === set.size)
    if (expected != null) assert(set === expected)
  }

  test("testDecompose_aba") {
    val expected = Set(
      "a|b|a|",
      "aba|"
    )
    run("aba", expected)
  }

  test("testDecompose_abracadabra") {
    val expected = Set(
      "a|b|r|aca|d|a|b|r|a|",
      "a|b|r|a|c|ada|b|r|a|",
      "a|b|r|a|c|a|d|a|b|r|a|"
    )
    run("abracadabra", expected)
  }

  test("testDecompose_neveroddoreven") {
    val expected = Set(
      "n|e|v|e|r|o|d|d|o|r|e|v|e|n|", 
      "n|e|v|e|r|o|d|d|o|r|eve|n|", 
      "n|e|v|e|r|o|dd|o|r|e|v|e|n|", 
      "n|e|v|e|r|o|dd|o|r|eve|n|", 
      "n|e|v|e|r|oddo|r|e|v|e|n|", 
      "n|e|v|e|r|oddo|r|eve|n|",
      "n|e|v|e|roddor|e|v|e|n|", 
      "n|e|v|e|roddor|eve|n|", 
      "n|e|v|eroddore|v|e|n|",
      "n|e|veroddorev|e|n|", 
      "n|eve|r|o|d|d|o|r|e|v|e|n|", 
      "n|eve|r|o|d|d|o|r|eve|n|",
      "n|eve|r|o|dd|o|r|e|v|e|n|", 
      "n|eve|r|o|dd|o|r|eve|n|", 
      "n|eve|r|oddo|r|e|v|e|n|",
      "n|eve|r|oddo|r|eve|n|", 
      "n|eve|roddor|e|v|e|n|", 
      "n|eve|roddor|eve|n|", 
      "n|everoddoreve|n|",
      "neveroddoreven|"
    )
    run("neveroddoreven", expected)
  }

  test("testDecompose_abcccba") {
    val expected = Set(
      "a|b|c|c|c|b|a|",
      "a|b|ccc|b|a|",
      "a|b|c|cc|b|a|",
      "a|b|cc|c|b|a|",
      "a|bcccb|a|",
      "abcccba|",
    )
    run("abcccba", expected)
  }

  test("testDecompose_aaaaaaaaaaaaaaaaaaaa") {
    run("aaaaaaaaaaaaaaaaaaaa", null)
  }
}