|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | | -/** |
4 | | - * 944. Delete Columns to Make Sorted |
5 | | - * |
6 | | - * We are given an array A of N lowercase letter strings, all of the same length. |
7 | | - * Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices. |
8 | | - * For example, if we have an array A = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, |
9 | | - * then the final array after deletions is ["bef", "vyz"], and the remaining columns of A are ["b","v"], ["e","y"], |
10 | | - * and ["f","z"]. (Formally, the c-th column is [A[0][c], A[1][c], ..., A[A.length-1][c]].) |
11 | | - * |
12 | | - * Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order. |
13 | | - * |
14 | | - * Return the minimum possible value of D.length. |
15 | | - * |
16 | | - * Example 1: |
17 | | - * |
18 | | - * Input: ["cba","daf","ghi"] |
19 | | - * Output: 1 |
20 | | - * Explanation: |
21 | | - * After choosing D = {1}, each column ["c","d","g"] and ["a","f","i"] are in non-decreasing sorted order. |
22 | | - * If we chose D = {}, then a column ["b","a","h"] would not be in non-decreasing sorted order. |
23 | | - * Example 2: |
24 | | - * |
25 | | - * Input: ["a","b"] |
26 | | - * Output: 0 |
27 | | - * Explanation: D = {} |
28 | | - * Example 3: |
29 | | - * |
30 | | - * Input: ["zyx","wvu","tsr"] |
31 | | - * Output: 3 |
32 | | - * Explanation: D = {0, 1, 2} |
33 | | - * |
34 | | - * |
35 | | - * Note: |
36 | | - * |
37 | | - * 1 <= A.length <= 100 |
38 | | - * 1 <= A[i].length <= 1000 |
39 | | - * */ |
40 | 3 | publicclass_944 { |
41 | | -publicstaticclassSolution1 { |
42 | | -publicintminDeletionSize(String[]A) { |
43 | | -if (A ==null ||A.length ==0) { |
44 | | -return0; |
45 | | - } |
46 | | -intdeletion =0; |
47 | | -for (inti =0;i <A[0].length();i++) { |
48 | | -for (intj =0;j <A.length -1;j++) { |
49 | | -if (A[j].charAt(i) >A[j +1].charAt(i)) { |
50 | | -deletion++; |
51 | | -break; |
52 | | - } |
| 4 | +publicstaticclassSolution1 { |
| 5 | +publicintminDeletionSize(String[]A) { |
| 6 | +if (A ==null ||A.length ==0) { |
| 7 | +return0; |
| 8 | + } |
| 9 | +intdeletion =0; |
| 10 | +for (inti =0;i <A[0].length();i++) { |
| 11 | +for (intj =0;j <A.length -1;j++) { |
| 12 | +if (A[j].charAt(i) >A[j +1].charAt(i)) { |
| 13 | +deletion++; |
| 14 | +break; |
| 15 | + } |
| 16 | + } |
| 17 | + } |
| 18 | +returndeletion; |
53 | 19 | } |
54 | | - } |
55 | | -returndeletion; |
56 | 20 | } |
57 | | - } |
58 | 21 | } |