列を削除して、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）の配列lisを定義し、これに1を入力します

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j

    • ok：=true

    • 初期化k：=0の場合、k

      • A [k、j]> A [k、i]の場合、

        • ok：=false

        • ループから出てきます

    • 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