删除列以在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