LeetCode Entry

131. Palindrome Partitioning

22.01.2023 medium 2023 kotlin

fun partition(s: String): List> {

131. Palindrome Partitioning medium

https://t.me/leetcode_daily_unstoppable/93

blog post

    fun partition(s: String): List<List<String>> {
        val dp = Array(s.length) { BooleanArray(s.length) { false } }
        for (from in s.lastIndex downTo 0)
            for (to in from..s.lastIndex)
                dp[from][to] = s[from] == s[to] && (from == to || from == to - 1 || dp[from+1][to-1])
        val res = mutableListOf<List<String>>()
        fun dfs(pos: Int, partition: MutableList<String>) {
            if (pos == s.length) res += partition.toList()
            for (i in pos..s.lastIndex)
                if (dp[pos][i]) {
                    partition += s.substring(pos, i+1)
                    dfs(i+1, partition)
                    partition.removeAt(partition.lastIndex)
                }
        }
        dfs(0, mutableListOf())
        return res
    }

First, we need to be able to quickly tell if some range a..b is a palindrome. Let’s dp[a][b] indicate that range a..b is a palindrome. Then the following is true: dp[a][b] = s[a] == s[b] && dp[a+1][b-1], also two corner cases, when a == b and a == b-1. For example, “a” and “aa”.

• Use dp for precomputing palindrome range answers.
• Try all valid partitions with backtracking.

Space: O(2^N), Time: O(2^N)