ধরুন আমাদের N স্ট্রিং এর একটি অ্যারে আছে। প্রতিটি স্ট্রিং ছোট হাতের অক্ষর নিয়ে গঠিত, সব একই দৈর্ঘ্যের। এখন, আমরা মুছে ফেলা সূচকগুলির যে কোনও সেট বেছে নিতে পারি এবং প্রতিটি স্ট্রিংয়ের জন্য, আমরা সেই সূচকগুলির সমস্ত অক্ষর মুছে ফেলব৷ এখন বিবেচনা করুন আমরা মুছে ফেলার সূচকগুলির একটি সেট 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) এবং এটি 1
দিয়ে পূরণ করুন -
আরম্ভ করার জন্য i :=0, যখন i
-
j শুরু করার জন্য :=0, যখন j
-
ঠিক আছে :=সত্য
-
আরম্ভ করার জন্য k :=0, যখন k
-
যদি A[k, j]> A[k, i], তাহলে
-
ঠিক আছে :=মিথ্যা
-
লুপ থেকে বেরিয়ে আসুন
-
-
-
যদি ok অ-শূন্য হয়, তাহলে −
-
lis[i] :=সর্বাধিক lis[j] + 1 এবং lis[i]
-
ret :=সর্বোচ্চ ret এবং lis[i]
-
-
-
-
যদি 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
