C++에서 정렬된 III를 만들기 위해 열 삭제

<시간/>

N개의 문자열로 구성된 배열 A가 있다고 가정합니다. 각 문자열은 소문자로 구성되며 모두 길이가 동일합니다. 이제 삭제 색인 세트를 선택할 수 있으며 각 문자열에 대해 해당 색인의 모든 문자를 삭제할 것입니다. 이제 삭제 후 최종 배열에 사전식의 모든 요소가 있도록 삭제 색인 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로 채웁니다.
initialize i :=0의 경우 i
- j:=0 초기화의 경우, j
  - 확인 :=사실
  - 초기화 k :=0의 경우 k
    - A[k, j]> A[k, i]이면
      - 확인 :=거짓
      - 루프에서 나오세요
  - ok가 0이 아니면 -
    - 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"}