leetcode [955] 删列造序 II

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定由 N 个小写字母字符串组成的数组 A，其中每个字符串长度相等。

选取一个删除索引序列，对于 A 中的每个字符串，删除对应每个索引处的字符。

比如，有 A = [“abcdef”, “uvwxyz”]，删除索引序列 {0, 2, 3}，删除后 A 为[“bef”, “vyz”]。

假设，我们选择了一组删除索引 D，那么在执行删除操作之后，最终得到的数组的元素是按 字典序（A[0] <= A[1] <= A[2] … <= A[A.length - 1]）排列的，然后请你返回 D.length 的最小可能值。

示例 1：

输入：["ca","bb","ac"]
输出：1
解释： 
删除第一列后，A = ["a", "b", "c"]。
现在 A 中元素是按字典排列的 (即，A[0] <= A[1] <= A[2])。
我们至少需要进行 1 次删除，因为最初 A 不是按字典序排列的，所以答案是 1。

示例 2：

输入：["xc","yb","za"]
输出：0
解释：
A 的列已经是按字典序排列了，所以我们不需要删除任何东西。
注意 A 的行不需要按字典序排列。
也就是说，A[0][0] <= A[0][1] <= ... 不一定成立。

示例 3：

输入：["zyx","wvu","tsr"]
输出：3
解释：
我们必须删掉每一列。

提示：

1 <= A.length <= 100
1 <= A[i].length <= 100

思路来自题解:

首先没有任意列保留，对于每一列：如果保留后结果保持有序，就保留这一列；否则删除它。

class Solution:
    def strangePrinter(self, s: str) -> int:
        if len(s) == 0: return 0
        memo = {}
        def dp(i, j):
            if i > j: return 0
            if (i, j) in memo:
                return memo[i, j]
            ans = dp(i + 1, j) + 1
            for k in range(i + 1, j + 1):
                if s[k] == s[i]:
                    ans = min(ans, dp(i, k - 1) + dp(k + 1, j))
            memo[i, j] = ans
            return memo[i, j]
        dp(0, len(s) - 1)
        return memo[0, len(s) - 1]