{"id":4337,"date":"2018-11-18T13:45:13","date_gmt":"2018-11-18T21:45:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4337"},"modified":"2018-11-18T13:50:00","modified_gmt":"2018-11-18T21:50:00","slug":"leetcode-944-delete-columns-to-make-sorted","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-944-delete-columns-to-make-sorted\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 944. Delete Columns to Make Sorted"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

We are given an array\u00a0A<\/code>\u00a0of\u00a0N<\/code>\u00a0lowercase letter strings, all of the same length.<\/p>\n

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

For example, if we have a string\u00a0\"<\/code>abcdef<\/code>\"<\/code>\u00a0and deletion indices\u00a0{0, 2, 3}<\/code>, then the final string after deletion\u00a0is\u00a0\"<\/code>bef<\/code>\"<\/code>.<\/p>\n

Suppose we chose a set of deletion indices\u00a0D<\/code>\u00a0such that after deletions, each remaining column in A is in\u00a0non-decreasing<\/strong>\u00a0sorted order.<\/p>\n

Formally, the\u00a0c<\/code>-th column is\u00a0[A[0][c], A[1][c], ..., A[A.length-1][c]]<\/code><\/p>\n

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

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

Input: <\/strong>[\"cba\",\"daf\",\"ghi\"]<\/span>\r\nOutput: <\/strong>1<\/span>\r\n<\/pre>\n
Example 2:<\/strong><\/p>\n
Input: <\/strong>[\"a\",\"b\"]<\/span>\r\nOutput: <\/strong>0<\/span>\r\n<\/pre>\n
Example 3:<\/strong><\/p>\n
Input: <\/strong>[\"zyx\",\"wvu\",\"tsr\"]<\/span>\r\nOutput: <\/strong>3<\/span>\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. 1 <= A.length <= 100<\/code><\/li>\n
  2. 1 <= A[i].length <= 1000<\/code><\/li>\n<\/ol>\n
    Solution: Simulation<\/strong><\/h1>\n
    Check descending case column by column.<\/p>\n
    Time complexity: O(NL)<\/p>\n
    Space complexity: O(1)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua, 64 ms\r\nclass Solution {\r\npublic:\r\n  int minDeletionSize(vector<string>& A) {\r\n    int ans = 0;\r\n    for (int c = 0; c < A[0].size(); ++c)\r\n      for (int r = 1; r < A.size(); ++r) {\r\n        if (A[r][c] < A[r - 1][c]) {\r\n          ++ans;\r\n          break;\r\n        }\r\n      }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem We are given an array\u00a0A\u00a0of\u00a0N\u00a0lowercase letter strings, all of the same length. Now, we may choose any set of deletion indices, and for each…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[177,179,4],"class_list":["post-4337","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-medium","tag-simulation","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4337","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=4337"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4337\/revisions"}],"predecessor-version":[{"id":4342,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4337\/revisions\/4342"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4337"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4337"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4337"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}