สมมติว่าเรามีสตริงอาร์เรย์ A ของ 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
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ยกเลิก :=0
-
n :=ขนาดของ A
-
m :=ขนาด A[0]
-
กำหนดรายการขนาดอาร์เรย์ (m + 1) และเติมด้วย 1
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
สำหรับการเริ่มต้น j :=0 เมื่อ j
-
โอเค :=จริง
-
สำหรับการเริ่มต้น k :=0 เมื่อ k
-
ถ้า A[k, j]> A[k, i] แล้ว
-
โอเค :=เท็จ
-
ออกจากวง
-
-
-
ถ้าตกลงไม่ใช่ศูนย์ ดังนั้น −
-
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
