题目是 Delete Columns to Make Sorted II
We are given an array A of N lowercase letter strings, all of the same length.
Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.
For example, if we have an array A = ["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 D such that after deletions, the final array has its elements in lexicographic order ( A[0] <= A[1] <= A[2] ... <= A[A.length - 1] ).
Return the minimum possible value of D.length .
Input: ["ca","bb","ac"]
Output: 1
Explanation:
After deleting the first column, A = ["a", "b", "c"].
Now A is in lexicographic order (ie. A[0] <= A[1] <= A[2]).
We require at least 1 deletion since initially A was not in lexicographic order, so the answer is 1.
Input: ["xc","yb","za"]
Output: 0
Explanation:
A is already in lexicographic order, so we don't need to delete anything.
Note that the rows of A are not necessarily in lexicographic order:
ie. it is NOT necessarily true that (A[0][0] <= A[0][1] <= ...)
Input: ["zyx","wvu","tsr"]
Output: 3
Explanation:
We have to delete every column.
Solution 的代码是
class Solution {
public int minDeletionSize(String[] A) {
int N = A.length;
int W = A[0].length();
int ans = 0;
// cur : all rows we have written
// For example, with A = ["abc","def","ghi"] we might have
// cur = ["ab", "de", "gh"].
String[] cur = new String[N];
for (int j = 0; j < W; ++j) {
// cur2 : What we potentially can write, including the
// newest column col = [A[i][j] for i]
// Eg. if cur = ["ab","de","gh"] and col = ("c","f","i"),
// then cur2 = ["abc","def","ghi"].
String[] cur2 = Arrays.copyOf(cur, N);
for (int i = 0; i < N; ++i)
cur2[i] += A[i].charAt(j);
if (isSorted(cur2))
cur = cur2;
else
ans++;
}
return ans;
}
public boolean isSorted(String[] A) {
for (int i = 0; i < A.length - 1; ++i)
if (A[i].compareTo(A[i+1]) > 0)
return false;
return true;
}
}
Leetcode 给的 Time Complexity: O(NW^2), where N is the length of A , and W is the length of A[i] . 这个说法有误吗？
从代码来看，外围的for loop是W， 里面的Array copy 是 N，里面的for loop是N，isSorted 是NW。所以total是 W * (N + N + NW) = NW^2 + 2WN ~= NW^2
为什么isSorted 是NW呢？
我们看下
public boolean isSorted(String[] A) {
for (int i = 0; i < A.length - 1; ++i)
if (A[i].compareTo(A[i+1]) > 0)
return false;
return true;
}
}
这里每次 A[i] 跟 A[i + 1]的比较 compareTo 的操作是W，加上for loop就是N * W。
所以 leetcode 的分析并没有错误。