C++で削除することによる辞書の最長の単語

文字列と文字列辞書があるとすると、指定された文字列の一部の文字を削除することで形成できる最長の文字列を辞書で見つける必要があります。考えられる結果が複数ある場合は、辞書式順序が最小の最長の単語を返します。結果がない場合は、空白の文字列を返します。したがって、入力が「abpcplea」のようで、d =[「ale」、「apple」、「monkey」、「plea」]の場合、結果は「apple」になります。

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

• isSubsequence（）というメソッドを定義します。これにはs1とs2が必要です
• j：=0
• 0からs1のサイズまでの範囲のiの場合
  • s2 [j] =s1 [i]の場合、jを1増やします
  • j =s2のサイズの場合、ループを解除します
• j=s2のサイズの場合はtrueを返します
• メインの方法から、次の手順を実行します-
• ans：=空白の文字列
• 範囲0からd–1のサイズのiの場合
  • x：=d [i]
  • xのサイズ>ansのサイズまたはxのサイズ=ansのサイズおよびx
  • isSubsequence（s、x）がtrueの場合、ans：=x

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool isSubsequence(string s1, string s2){
      int j =0;
      for(int i = 0; i < s1.size(); i++){
         if(s2[j] == s1[i]){
            j++;
            if(j == s2.size()) break;
         }
      }
      return j == s2.size();
   }
   string findLongestWord(string s, vector<string>& d) {
      string ans = "";
      for(int i = 0; i < d.size(); i++){
         string x = d[i];
         if(x.size() > ans.size() || (x.size() == ans.size() && (x < ans))){
            if(isSubsequence(s, x)) ans = x;
         }
      }
      return ans;
   }
};
main(){
   vector<string> v = {"ale","apple","monkey","plea"};
   Solution ob;
   cout << (ob.findLongestWord("abpcplea", v));
}

入力

"abpcplea"
["ale","apple","monkey","plea"]

出力

apple