Xóa các cột để sắp xếp III trong C ++

Giả sử chúng ta có một mảng A gồm N chuỗi. Mỗi chuỗi bao gồm các chữ cái viết thường, tất cả đều có cùng độ dài. Bây giờ, chúng ta có thể chọn bất kỳ tập hợp chỉ số xóa nào và đối với mỗi chuỗi, chúng ta sẽ xóa tất cả các ký tự trong các chỉ số đó. trình tự.

Để rõ ràng, A [0] theo thứ tự từ vựng (Vì vậy A [0] [0] <=A [0] [1] <=... <=A [0] [n - 1]), A [1 ] theo thứ tự từ vựng (tức là. A [1] [0] <=A [1] [1] <=... <=A [1] [n - 1]), v.v. (Ở đây n là kích thước của các chuỗi). Chúng ta phải tìm giá trị nhỏ nhất có thể có của kích thước D.

Vì vậy, nếu đầu vào là ["cbcdb", "ccbxc"], thì đầu ra sẽ là 3

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0

• n:=kích thước của A

• m:=kích thước của A [0]

• Xác định lis mảng có kích thước (m + 1) và điền vào giá trị này bằng 1

• để khởi tạo i:=0, khi i

  • để khởi tạo j:=0, khi j

    • ok:=true

    • để khởi tạo k:=0, khi k

      • nếu A [k, j]> A [k, i] thì

        • ok:=false

        • Ra khỏi vòng lặp

    • nếu ok là khác 0 thì -

      • lis [i]:=tối đa lis [j] + 1 và lis [i]

      • ret:=tối đa ret và lis [i]

• nếu ret giống 0 thì -

  • trả về m - 1

• trả lại m - ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{"cbcdb","ccbxc"}

Đầu ra

3