删除列以在C ++中进行排序III

假设我们有一个由N个字符串组成的数组A。每个字符串均由小写字母组成，且长度均相同。现在，我们可以选择任何一组删除索引，并且对于每个字符串，我们将删除这些索引中的所有字符。现在考虑我们采用了一组删除索引D，以便在删除之后，最终数组具有字典序中的每个元素顺序。

为了清楚起见，A [0]按字典顺序排序（因此A [0] [0] <= A [0] [1] <= ... <= A [0] [n-1]），A [1 ]以字典顺序排列（即A [1] [0] <= A [1] [1] <= ... <= A [1] [n-1]），依此类推。（这里n是字符串的大小）。我们必须找到D大小的最小可能值。

因此，如果输入类似于[“ cbcdb”，“ ccbxc”]，则输出将为3

为了解决这个问题，我们将遵循以下步骤-

• ret：= 0

• n：= A的大小

• m：= A [0]的大小

• 定义大小为（m + 1）的数组lis，并用1填充

• 对于初始化i：= 0，当i <m时，更新（将i增加1），执行-

• 好的：=真

• 对于初始化k：= 0，当k <n时，更新（将k增加1），-

• 如果ok不为零，则-

• 好的：=假

• 从循环中出来

• 如果A [k，j]> A [k，i]，则

• lis [i]：= lis [j] + 1和lis [i]的最大值

• ret：= ret和lis [i]的最大值

• 对于初始化j：= 0，当j <i时，更新（将j增加1），执行-

• 如果ret与0相同，则-

• 返回m-1

• 返回m-ret

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minDeletionSize(vector<string>& A){
      int ret = 0;
      int n = A.size();
      int m = A[0].size();
      vector<int> lis(m + 1, 1);
      for (int i = 0; i < m; i++) {
         for (int j = 0; j < i; j++) {
            bool ok = true;
            for (int k = 0; k < n; k++) {
               if (A[k][j] > A[k][i]) {
                  ok = false;
                  break;
               }
            }
            if (ok) {
               lis[i] = max(lis[j] + 1, lis[i]);
               ret = max(ret, lis[i]);
            }
         }
      }
      if (ret == 0)
      return m - 1;
      return m - ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"cbcdb","ccbxc"};
   cout << (ob.minDeletionSize(v));
}

输入值

{"cbcdb","ccbxc"}

输出结果

3