मान लीजिए कि हमारे पास एन स्ट्रिंग्स का एक एरे ए है। प्रत्येक स्ट्रिंग में लोअरकेस अक्षर होते हैं, सभी समान लंबाई के होते हैं। अब, हम विलोपन सूचकांकों का कोई भी सेट चुन सकते हैं, और प्रत्येक स्ट्रिंग के लिए, हम उन सूचकांकों के सभी वर्णों को हटा देंगे। अब विचार करें कि हमने विलोपन सूचकांक D का एक सेट लिया है, जैसे कि विलोपन के बाद, अंतिम सरणी में लेक्सिकोग्राफिक में प्रत्येक तत्व होता है। अनुक्रम।
स्पष्टता के लिए, A[0] शब्दावली क्रम में है (इसलिए A[0][0] <=A[0][1] <=... <=A[0][n - 1]), A[1 ] शब्दावली क्रम में है (यानी ए [1] [0] <=ए [1] [1] <=... <=ए [1] [एन -1]), और इसी तरह। (यहाँ n स्ट्रिंग्स का आकार है)। हमें D के आकार का न्यूनतम संभव मान ज्ञात करना है।
इसलिए, यदि इनपुट ["cbcdb",,"ccbxc"] जैसा है, तो आउटपुट 3
होगाइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
रिट:=0
-
n :=A का आकार
-
मी:=ए का आकार[0]
-
आकार की एक सरणी सूची को परिभाषित करें (m + 1) और इसे 1
. से भरें -
इनिशियलाइज़ करने के लिए मैं :=0, जब i
-
इनिशियलाइज़ j :=0 के लिए, जब j
-
ठीक :=सच
-
इनिशियलाइज़ k :=0 के लिए, जब k
-
अगर A[k, j]> A[k, i], तो
-
ठीक :=असत्य
-
लूप से बाहर आएं
-
-
-
यदि ठीक गैर-शून्य है, तो -
-
लिस[i] :=अधिकतम लिस[j] + 1 और लिस[i]
-
रिट :=अधिकतम रिट और लिस[i]
-
-
-
-
अगर रिट 0 के समान है, तो -
-
वापसी एम - 1
-
-
वापसी एम - रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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