C++で最長の文字列チェーン

単語のリストがあるとします。ここでは、各単語は小文字で構成されています。したがって、ある単語word1は、別の単語word2の前身であり、word1の任意の場所に正確に1文字を追加して、word2と等しくすることができる場合に限ります。前任者の例は次のようになります。「abc」は「abac」の前任者です。ここで、ワードチェーンはk> =1の一連の単語[word_1、word_2、...、word_k]です。ここで、word_1はword_2の先行であり、word_2はword_3の先行です。与えられた単語のリストから選択された単語を使用して、単語チェーンの可能な限り長い長さを見つける必要があります。

したがって、入力が["a"、 "b"、 "ba"、 "bca"、 "bda"、 "bdca"]の場合、最長のチェーンの1つが[" a」、「ba」、「bda」、「bdca」]。

これを解決するには、次の手順に従います-

• マップを定義するdp、n：=単語配列のサイズ

• 長さに基づいて単語配列を並べ替える

• ret：=0

• 範囲0tnn –1のiの場合

  • 最高：=0

  • 0から単語の長さまでの範囲のjの場合[i]– 1

    • word：=（0からj – 1までのwords[i]の部分文字列）連結（j + 1から最後までのwords[i]の部分文字列）

    • 最高：=最高の最大、dp [word] + 1

  • dp [words [i]]：=最高

  • ret：=max of（ret、dp [words [i]]）

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   static bool cmp(string s1, string s2){
      return s1.size() < s2.size();
   }
   int longestStrChain(vector<string>& words) {
      unordered_map <string, int> dp;
      int n = words.size();
      sort(words.begin(), words.end(), cmp);
      int ret = 0;
      for(int i = 0; i < n; i++){
         int best = 0;
         for(int j = 0; j < words[i].size(); j++){
            string word = words[i].substr(0, j) +
            words[i].substr(j + 1);
            best = max(best, dp[word] + 1);
         }
         dp[words[i]] = best;
         ret = max(ret, dp[words[i]]);
      }
      return ret;
   }
};
main(){
   vector<string> v = {"a","b","ba","bca","bda","bdca"};
   Solution ob;
   cout << (ob.longestStrChain(v));
}

入力

["a","b","ba","bca","bda","bdca"]

出力

4