955. Delete Columns to Make Sorted II删列造序

 1import java.util.Arrays;
 2
 3/**
 4 * @author lxn
 5 * @description 955. Delete Columns to Make Sorted II
 6 * @create 2020-02-18 20:56
 7 */
 8public class Algorithm955 {
 9    public static void main(String[] args) {
10        String[] A = {"ca", "bb", "ac"};
11        int res = new Solution955().minDeletionSize(A);
12    }
13}
14
15class Solution955 {
16    public int minDeletionSize(String[] A) {
17        int N = A.length;
18        int W = A[0].length();
19        int res = 0;
20
21        String[] cur = new String[N];
22        for (int j = 0; j < W; ++j) { // 遍历第几个index
23            // j = 0, cur = {null, null, null}; j = 1, 也都是null; j = 2, cur = {"nulla", "nullb", "nullc"};
24            // copy cur数组，如果N比cur的长度大，那么多出的用null(因为是String，如果是int，那就用0填充)填充。
25            // 为什么要用cur2呢？内层for循环要给cur2赋值。而cur的话，只有当前i的字符们是字典序的时候才会接受cur2的赋值。
26            String[] cur2 = Arrays.copyOf(cur, N);
27            for (int i = 0; i < N; ++i) // 遍历第几个元素(字符串)
28                cur2[i] += A[i].charAt(j);// j=0, cur2 = {"nullc", "nullb", "nulla"}; j=1, cur2={"nullb", "nullb", "nullc"};
29
30            // 如果这些字符串是按字典序，那就cur2赋值给cur。赋值给它有什么用处呢？因为外层for循环的时候还会用到这个cur。
31            if (isSorted(cur2)) cur = cur2;// 是字典序
32            else res++; // 不是字典序，说明要删除index加1
33        }
34
35        return res;
36    }
37
38    // 按字典序排序
39    private boolean isSorted(String[] A) {
40        for (int i = 0; i < A.length - 1; ++i) {
41            // compareTo(): 按字典序比较，若此字符串大于字符串参数，则返回一个大于 0 的值
42            if (A[i].compareTo(A[i + 1]) > 0) return false;
43        }
44
45        return true;
46    }
47}