Package g0901_1000.s0944_delete_columns_to_make_sorted

Class Solution

java.lang.Object
g0901_1000.s0944_delete_columns_to_make_sorted.Solution
public class Solution extends Object
944 - Delete Columns to Make Sorted.<p>Easy</p> <p>You are given an array of <code>n</code> strings <code>strs</code>, all of the same length.</p> <p>The strings can be arranged such that there is one on each line, making a grid. For example, <code>strs = [&quot;abc&quot;, &quot;bce&quot;, &quot;cae&quot;]</code> can be arranged as:</p> <pre><code> abc bce cae </code></pre> <p>You want to <strong>delete</strong> the columns that are <strong>not sorted lexicographically</strong>. In the above example (0-indexed), columns 0 (<code>'a'</code>, <code>'b'</code>, <code>'c'</code>) and 2 (<code>'c'</code>, <code>'e'</code>, <code>'e'</code>) are sorted while column 1 (<code>'b'</code>, <code>'c'</code>, <code>'a'</code>) is not, so you would delete column 1.</p> <p>Return <em>the number of columns that you will delete</em>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> strs = [&ldquo;cba&rdquo;,&ldquo;daf&rdquo;,&ldquo;ghi&rdquo;]</p> <p><strong>Output:</strong> 1</p> <p><strong>Explanation:</strong> The grid looks as follows:</p> <pre><code> cba daf ghi </code></pre> <p>Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> strs = [&ldquo;a&rdquo;,&ldquo;b&rdquo;]</p> <p><strong>Output:</strong> 0</p> <p><strong>Explanation:</strong> The grid looks as follows:</p> <pre><code> a b </code></pre> <p>Column 0 is the only column and is sorted, so you will not delete any columns.</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> strs = [&ldquo;zyx&rdquo;,&ldquo;wvu&rdquo;,&ldquo;tsr&rdquo;]</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> The grid looks as follows:</p> <pre><code> zyx wvu tsr </code></pre> <p>All 3 columns are not sorted, so you will delete all 3.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>n == strs.length</code></li> <li><code>1 <= n <= 100</code></li> <li><code>1 <= strs[i].length <= 1000</code></li> <li><code>strs[i]</code> consists of lowercase English letters.</li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • minDeletionSize

      public int minDeletionSize(String[] strs)