[数据结构与算法]LeetCode每日一题(Delete Columns to Make Sorted II)

You are given an array of n strings strs, all of the same length.

We may choose any deletion indices, and we delete all the characters in those indices for each string.

For example, if we have strs = [“abcdef”,“uvwxyz”] and deletion indices {0, 2, 3}, then the final array after deletions is [“bef”, “vyz”].

Suppose we chose a set of deletion indices answer such that after deletions, the final array has its elements in lexicographic order (i.e., strs[0] <= strs[1] <= strs[2] <= … <= strs[n - 1]). Return the minimum possible value of answer.length.

Example 1:

Input: strs = [“ca”,“bb”,“ac”]
Output: 1

Explanation:

After deleting the first column, strs = [“a”, “b”, “c”].
Now strs is in lexicographic order (ie. strs[0] <= strs[1] <= strs[2]).
We require at least 1 deletion since initially strs was not in lexicographic order, so the answer is 1.
Example 2:

Input: strs = [“xc”,“yb”,“za”]
Output: 0

Explanation:

strs is already in lexicographic order, so we do not need to delete anything.
Note that the rows of strs are not necessarily in lexicographic order:
i.e., it is NOT necessarily true that (strs[0][0] <= strs[0][1] <= …)

Example 3:

Input: strs = [“zyx”,“wvu”,“tsr”]
Output: 3

Explanation:

We have to delete every column.

Constraints:

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

这是这段时间以来做过的最令我激动的题目，一路骂着娘做下来的。思路不复杂，实现要人命，再加上rust对字符串的处理又不太方便，造成中间一度想砸显示器。

这题我不知道有没有其他的解决方法，但是开始试了两次之后，我的思路基本就形成了：

1. 依次检查每个单词的第i个字母, 与前一个单词的第i个字母进行对比， 如果小于前一个单词的第i个字母则退出循环，删除列的计数加1， 因为这一列存在逆序的排列，所以整列都需要删除。
2. 经过步骤1之后，我们可以得知所有单词的第i个字母是正序排列的，也就是strs[n][i] <= strs[n+1][i], 小于的没有什么异议，我们可以直接判定它们一定是按字母顺序排列的，但是等于的就没有这么简单了，我们要把第i个字母相同的字符串分到一组中，这样我们对每一组的字符串再进行第i+1个字母的判断, 但是这若干个组依然要看做一个整体，有一个组检查出逆序，整个i+n列都要被删除。

写到这我发现这鬼题目就连想把想法说清楚都很难，我们可以把原始的字符串数组看做一个char的矩阵。比如

["iax", "haz", "gcd", "fce", "edw"]
我们可以看成

[
    ['i', 'a', 'x' ],
    ['h', 'a', 'z' ],
    ['g', 'c', 'd' ],
    ['f', 'c', 'e' ],
    ['e', 'd', 'w' ],
]

假设count为最终需要删除列的计数
我们先来看第一列:

['i', 'h', 'g', 'f', 'e']

i > h > g > f > e, 都是逆序的， 所以这一列需要删除(只要有一个逆序就要删除)， count++

矩阵变成:

[
    ['a', 'x' ],
    ['a', 'z' ],
    ['c', 'd' ],
    ['c', 'e' ],
    ['d', 'w' ],
]

我们接着往下看

['a', 'a', 'c', 'c', 'd']

a = a < c = c < d, 没有逆序，但是有相等， 这时我们只需要把字符相等的字符串组成一组进行后面的判断就好了, d因为没有重复，所以我们可以忽略掉它了

于是剩下的字符矩阵变成了

[
    [
        ['x'],
        ['z'],
    ],
    [
        ['d'],
        ['e'],
    ]
]

第一组x < z, 可以宣告成立， 第二组, d < e, 也宣告成立，于是可以返回count了。
之所以分组是因为每组只需要组内正序就可以，与其他组的无关，因为每组其实都是按前一个字母正序排列的。

我已经尽力说清楚了，不过我实在不知道这种从左到右，高度收窄，并且还要进行分组对比，并且还要保持BFS的搜索方式应该怎么描述。总之我感觉很变态。

代码实现(Rust):

impl Solution {

    fn is_valid(list: &Vec<Vec<char>>) -> bool {
        for i in 1..list.len() {
            if list[i][0] < list[i-1][0] {
                return false;
            }
        }
        true
    }

    fn group(list: Vec<Vec<char>>) -> Vec<Vec<Vec<char>>> {
        let mut res: Vec<Vec<Vec<char>>> = Vec::new();
        for c in list  {
            if let Some(last) = res.last_mut() {
                if last[0][0] == c[0] {
                    last.push(c);
                    continue;
                } 
            }
            res.push(vec![c]);
        }
        res.into_iter().filter(|v| v.len() > 1).map(|mut l| {
            l.iter_mut().for_each(|c| { c.remove(0); });
            l
        }).collect()
    }

    fn delete(mut groups: Vec<Vec<Vec<char>>>, length: usize, ans: &mut i32) {
        if length == 0 {
            return;
        }
        if groups.is_empty() {
            return;
        }
        let mut new_groups: Vec<Vec<Vec<char>>> = Vec::new();
        for i in 0..groups.len() {
            if !Solution::is_valid(&groups[i]) {
                groups.iter_mut().for_each(|g| g.iter_mut().for_each(|c| { c.remove(0); }));
                *ans += 1;
                Solution::delete(groups, length - 1, ans);
                return;
            } 
            new_groups.extend(Solution::group(groups[i].clone()));
        }
        Solution::delete(new_groups, length-1, ans);
    }

    pub fn min_deletion_size(strs: Vec<String>) -> i32 {
        let length = strs[0].len();
        let groups: Vec<Vec<Vec<char>>> = vec![strs.into_iter().map(|s| s.chars().collect()).collect()];
        let mut count = 0;
        Solution::delete(groups, length, &mut count);
        count
    }
}