944. Delete Columns to Make Sorted

Link: https://leetcode.com/problems/delete-columns-to-make-sorted/

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”], and the remaining columns of A are [“b”,”v”], [“e”,”y”], and [“f”,”z”]. (Formally, the c-th column is [A[0][c], A[1][c], …, A[A.length-1][c]].)

Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.

Return the minimum possible value of D.length.

Example 1:

Input: ["cba","daf","ghi"]
Output: 1
Explanation:
After choosing D = {1}, each column ["c","d","g"] and ["a","f","i"] are in non-decreasing sorted order.
If we chose D = {}, then a column ["b","a","h"] would not be in non-decreasing sorted order.

Example 2:

Input: ["a","b"]
Output: 0
Explanation: D = {}

Example 3:

Input: ["zyx","wvu","tsr"]
Output: 3
Explanation: D = {0, 1, 2}

Note:

• 1 <= A.length <= 100
• 1 <= A[i].length <= 1000

---

題目翻譯:

我們給出了一個 N 個小寫字母串的數組 A，它們的長度都相同。

現在，我們可以選擇任何一組刪除索引，對於每個字符串，我們刪除這些索引中的所有字符。

例如，如果我們有一個數組 A = [“abcdef”，”uvwxyz”]和刪除索引{0,2,3}，那麼刪除後的最後一個數組是[“bef”，”vyz”]，以及 A 的剩餘列是[“b”，”v”]，[“e”，”y”]和[“f”，”z”]。 （形式上，第 c 列是[A [0][c]，A [1][c]，…，A [A.length-1][c]]。）

假設我們選擇了一個一組刪除索引 D 使得在刪除之後，A 中的每個剩餘列處於非遞減排序順序。

返回 D.length 的最小可能值。

程式思路:

用 dfs 來實作此題目。

class Solution {
public:
    int minDeletionSize(vector<string>& A) {
        int result = 0;
        for(int j = 0;j < A[0].length();j++)
        {
            for(int i = 0; i < A.size()-1 ;i++)
            {
                if(A[i][j] > A[i+1][j])
                {
                    result ++;
                    break;
                }
            }
        }
        return result;
    }
};