{"id":4505,"date":"2018-12-19T21:49:15","date_gmt":"2018-12-20T05:49:15","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4505"},"modified":"2018-12-19T23:18:41","modified_gmt":"2018-12-20T07:18:41","slug":"leetcode-960-delete-columns-to-make-sorted-iii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-960-delete-columns-to-make-sorted-iii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 960. Delete Columns to Make Sorted III"},"content":{"rendered":"\n

We are given an array A<\/code> of N<\/code> lowercase letter strings, all of the same length.<\/p>\n\n\n\n

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.<\/p>\n\n\n\n

For example, if we have an array A = [\"babca\",\"bbazb\"]<\/code> and deletion indices {0, 1, 4}<\/code>, then the final array after deletions is [\"bc\",\"az\"]<\/code>.<\/p>\n\n\n\n

Suppose we chose a set of deletion indices D<\/code> such that after deletions, the final array has every element (row) in lexicographic<\/strong> order.<\/p>\n\n\n\n

For clarity, A[0]<\/code> is in lexicographic order (ie. A[0][0] <= A[0][1] <= ... <= A[0][A[0].length - 1]<\/code>), A[1]<\/code> is in lexicographic order (ie. A[1][0] <= A[1][1] <= ... <= A[1][A[1].length - 1]<\/code>), and so on.<\/p>\n\n\n\n

Return the minimum possible value of D.length<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>[\"babca\",\"bbazb\"]\nOutput: <\/strong>3\nExplanation: <\/strong>After deleting columns 0, 1, and 4, the final array is A = [\"bc\", \"az\"].\nBoth these rows are individually in lexicographic order (ie. A[0][0] <= A[0][1] and A[1][0] <= A[1][1]).\nNote that A[0] > A[1] - the array A isn't necessarily in lexicographic order.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>[\"edcba\"]\nOutput: <\/strong>4\nExplanation: <\/strong>If we delete less than 4 columns, the only row won't be lexicographically sorted.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input: <\/strong>[\"ghi\",\"def\",\"abc\"]\nOutput: <\/strong>0\nExplanation: <\/strong>All rows are already lexicographically sorted.\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 1 <= A.length <= 100<\/code><\/li>
  2. 1 <= A[i].length <= 100<\/code><\/li><\/ol>\n\n\n\n
    Solution: DP<\/strong><\/h1>\n\n\n\n
    dp[i] := max length of increasing sub-sequence (of all strings) ends with i-th letter.
    dp[i] = max(dp[j] + 1) if all A[*][j] <= A[*][i], j < i
    Time complexity: (n*L^2)
    Space complexity: O(L)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n\n
    \n\/\/ Author: Huahua, running time: 24 ms\nclass Solution {\npublic:\n  int minDeletionSize(vector& A) {\n    vector dp(A[0].length(), 1);\n    for (int i = 0; i < A[0].length(); ++i)\n      for (int j = 0; j < i; ++j) {\n        bool valid = true;\n        for (const auto& a : A)\n          if (a[j] > a[i]) {\n            valid = false;\n            break;\n          }\n        if (valid) dp[i] = max(dp[i], dp[j] + 1);\n      }\n    return A[0].length() - *max_element(begin(dp), end(dp));\n  }\n};\n<\/pre>\n\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 176 ms\nclass Solution:\n  def minDeletionSize(self, A):\n    n = len(A[0])\n    dp = [1] * n\n    for i in range(1, n):\n      for j in range(i):\n        valid = True\n        for a in A:\n          if a[j] > a[i]: \n            valid = False\n            break\n        if valid:\n          dp[i] = max(dp[i], dp[j] + 1)\n    return n - max(dp)\n<\/pre>\n\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,217,305,229],"class_list":["post-4505","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-increasing","tag-subsequence","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4505","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4505"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4505\/revisions"}],"predecessor-version":[{"id":4509,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4505\/revisions\/4509"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4505"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4505"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4505"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}