LeetCode 955. Delete Columns to Make Sorted II

Delete Columns to Make Sorted II Medium

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.

完整介绍 https://leetcode.com/problems/delete-columns-to-make-sorted-ii/

这题有点难的是要看懂题目，要删到让所有的词都依词典顺序的排列
做法如下

由左往右，每一列再由上往下，把自己和下一行的字母拿来比，会有三种可能性

当 Repeat 都没有的时候，程式结束，回传 answer (砍掉几行)

範例题目

有重覆的字母以 R (Repeat)代表

执行完第一列，会 mark 出两个地方有重覆的字母

后续执行没必要再检查的字母以 「-」表示
执行完第二列，index 2 的 R 会被移除，目标把 R 移光就搞定收工了

执行第三列会发现这列必须删除，所以 answer + 1

执行完第四列后，将 R 全数移光，程式即结束，得到 answer 是 1

程式码

public class A0955_DeleteColumnsToMakeSortedII {    public int minDeletionSize(String[] strs) {    int ans = 0;    int[] sameNote = new int[strs.length]; // x 轴的长度 (上到下)    // x 轴往右走    for (int x=0; x<strs[0].length(); x++) {        int[] tmpSameNote = sameNote.clone();    boolean isAllLess = true;    boolean isDelete = false;    // y 轴往下走，最后一行不用，所以 -1    for (int y=0; y<strs.length-1; y++) {    if (sameNote[y] == -1)    continue;        char c1 = strs[y].charAt(x);    char c2 = strs[y+1].charAt(x);    if (c1 > c2) {    ans++;    isDelete = true;    break;    }    else if (c1 == c2) {    isAllLess = false;    }    else {    tmpSameNote[y] = -1;        }    }    if (! isDelete) {    sameNote = tmpSameNote;    if (isAllLess)        break;    }    }    return ans;    }}

unit test code

public class A0955_DeleteColumnsToMakeSortedIITest {@Testpublic void testMinDelete() {A0955_DeleteColumnsToMakeSortedII obj = new A0955_DeleteColumnsToMakeSortedII();assertEquals(1, obj.minDeletionSize(new String[] {"ca","bb","ac"}));assertEquals(0, obj.minDeletionSize(new String[] {"xc","yb","za"}));assertEquals(1, obj.minDeletionSize(new String[] {"xga","xfb","yfa"}));assertEquals(3, obj.minDeletionSize(new String[] {"zyx","wvu","tsr"}));assertEquals(1, obj.minDeletionSize(new String[] {"azzzhs","bayygo","ccxxfn", "cdooem", "eznndl", "fzmmck", "fzaxbj", "gzzaai"}));}}