LeetCode 2002. Максимальное произведение длины двух палиндромных подпоследовательностей.

Заметки LeetCode [44]

Проблема

Подход 1: ДФС

Найдите все возможные подпоследовательности, используя DFS, а затем найдите непересекающиеся подпоследовательности с максимальным произведением длины.

Выполнение

class Solution {
    private var candidates = mutableListOf<List<Int>>()
    fun maxProduct(s: String): Int {
        candidates = mutableListOf()
        search(s, listOf(), 0)
        return calculate()
    }

    private fun calculate(): Int {
        var max = Int.MIN_VALUE
        for (i in candidates.indices) {
            val p1 = candidates[i]
            for (j in i + 1 until candidates.size) {
                val p2 = candidates[j]
                if (!p1.any { it in p2 }) {
                    val mul = p1.size * p2.size
                    if (mul > max) {
                        max = mul
                    }
                }
            }
        }
        return max
    }

    private fun search(s: String, list: List<Int>, curIndex: Int) {
        if (curIndex < s.length) {
            val newList = list.toMutableList()
            search(
                s,
                newList.apply { add(curIndex) },
                curIndex + 1
            )
            search(s, list, curIndex + 1)
        } else {
            var result = ""
            list.forEach {
                result += s[it]
            }
            if (isPalindromic(result)) {
                candidates.add(list)
            }
        }
    }

    private fun isPalindromic(s: String): Boolean {
        if (s.isEmpty()) return false
        for (i in 0..s.length / 2) {
            if (s[i] != s[s.length - 1 - i])
                return false
        }
        return true
    }
}

Анализ сложности

• Временная сложность: O(sigma_0_n(2^n))
• Сложность пространства: O(n* 2^n)

Подход 2: улучшенная DFS

Так как для каждого символа c в заданной строке s, c будет либо

• In subsequence1
• In subsequence2
• Ни в subsequence1, ни в subsequence2

Повторение будет:

• If i < s.length,

F(i, s1, s2) = max(
    F(i+1, s1 + c, s2),
    F(i+1, s1, s2 + c),
    F(i+1, s1, s2)
)

• Если i == s.length и оба s1 и s2 являются палиндромами, вернуть произведение их длины.

Выполнение

class Solution {
    private var max = Int.MIN_VALUE

    private fun isPalindromic(s: String): Boolean {
        if (s.isEmpty()) return false
        for (i in 0..s.length / 2) {
            if (s[i] != s[s.length - 1 - i])
                return false
        }
        return true
    }

    fun maxProduct(s: String): Int {
        max = Int.MIN_VALUE
        search(s, 0, "", "")
        return max
    }

    private fun search(s: String, index: Int, s1: String, s2: String) {
        if (index < s.length) {
            search(s, index + 1, s1 + s[index], s2)
            search(s, index + 1, s1, s2 + s[index])
            search(s, index + 1, s1, s2)
        } else {
            if (isPalindromic(s1) && isPalindromic(s2)) {
                val mul = s1.length * s2.length
                if (mul > max) {
                    max = mul
                }
            }
        }
    }
}

Анализ сложности

• Временная сложность: O(sigma_0_n(3^n))
• Сложность пространства: O(n)