algorithm - minimum columns to be deleted in a matrix to make it row-wise lexicographically sorted
问题描述
I was trying to solve this hiring contest problem (now closed)
Lexicographic Rows
You are given a matrix of characters. In one operation you can remove a column of the matrix. You can perform as many operations as you want. Your task is to make the final matrix interesting i.e. the string formed by the characters of row is lexicographically smaller or equal to the string formed by the characters of the row. You need to use minimum number of operations possible. An empty matrix is always a interesting matrix.
Input
The first line contains two integers and . The next lines contain letters each.
Output
In the output, you need to print the minimum number of operations to make the matrix interesting.
Constraints
There are only lowercase English alphabets as characters in the input.
Sample Input
3 3
cfg
agk
dlm
Sample Output
1
Explanation
Delete the first column to make the matrix interesting.
I'm pretty convinced this is a DP problem. I was having difficulties finding the optimal subproblem though. I managed to pass only a couple of test cases
I defined dp[i][j]
as the minimum number of the columns to be removed to have an interesting matrix.
And for every character input[i][j]
there are two possibilities.
- if the previous entry is lexicographically valid we can take
dp[i][j - 1]
and the current input isn't going to change anything. - else we check if the
input[i -1][j]
andinput[i][j]
if they are in the correct order we considerdp[i][j - 1]
else this column is invalid too so we add1
todp[i][j-1]
My soln. code
int n, m;
cin >> n >> m;
vector<string> input(n);
for (int i = 0; i < n; ++i) {
string temp = "";
for (int j = 0; j < m; ++j) {
char c;
cin >> c;
temp = temp + c;
}
input[i] = temp;
}
vector<vector<int> > dp(n, vector<int>(m, 0));
for (int i = 1; i < n; ++i) {
for (int j = 1; j < m; ++j) {
//Left is valid
if (input[i - 1][j - 1] < input[i][j - 1]) {
dp[i][j] = dp[i][j - 1];
}
else {
//Current is valid
if (input[i - 1][j] <= input[i][j]) {
dp[i][j] = dp[i][j - 1];
}
else {
dp[i][j] = dp[i][j - 1] + 1;
}
}
}
}
cout << dp[n - 1][m - 1] << endl;
解决方案
我们可以从左到右遍历列,选择包含不会使当前矩阵无趣的列。如果实施得当,这将花费与输入大小成线性关系的时间。
支持该算法的关键事实是,给定两个有趣的列子集,我们可以将缺少的第一列从一个列添加到另一个列,而不会使其无趣。
推荐阅读
- node.js - express-handlebars:使用标签链接到车把
- pytorch - 生成随机种子以播种 Pytorch 的最佳实践?
- c++ - 了解 DCL60-CPP 中的不合规代码示例:遵守单一定义规则
- safari - Safari和Chrome中div内图像之间不需要的水平填充
- elasticsearch - 如何从 Kibana 仪表板添加包含过滤器?
- c# - VS2019 Find 进入死循环
- javascript - 尝试导入项目时出现错误“对每个 HTML 规范的模块脚本强制执行严格的 MIME 类型检查”
- excel - 如何从 ms-excel 的另一列中删除相同的单词?
- amazon-web-services - 如何从 aws lambda 函数的标头中检索 x-api-key
- r - R中的正则表达式和str_detect()