C++で文字列を形成する最短の方法

文字列があるとすると、いくつかの文字を削除することで（おそらく削除なしで）、その文字列のサブシーケンスを形成できます。したがって、sourceとtargetの文字列が2つある場合、それらの連結がtargetと等しくなるように、sourceのサブシーケンスの最小数を見つける必要があります。タスクが不可能な場合は、-1を返します。したがって、ソースが「abc」でターゲットが「abcbc」の場合、出力は2になります。

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

• possibleという文字列を定義します。これはsとtを入力として受け取ります

• マップを作成するm

• sマークの各文字cについてm[c]：=1

• tの各文字cについて、m [c]が0の場合、falseを返します

• trueを返す

• ここで、mainメソッドから、次のようにします-

• ssz：=sのサイズとtsz：=tのサイズ

• 文字型キーと配列型値のマップmを作成する

• 0からsszの範囲のiの場合

  • iをm[s[i]]

    に挿入します

• pre：=-1およびret：=1

• 0からtszの範囲のiの場合

  • t [i]がmに存在しない場合は、-1を返します

  • v：=m [t [i]]

  • set i：=vの要素のインデックス。preよりも大きい

  • 私がリストの最後でない場合

    • retを1増やし、pre：=v [0]

  • それ以外の場合はpre：=v [i]

• retを返す

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool possible(string s, string t){
      map <char, int> m;
      for(int i = 0; i < s.size(); i++){
         m[s[i]] = 1;
      }
      for(int i = 0; i < t.size(); i++){
         if(!m[t[i]])return false;
      }
      return true;
   }
   int shortestWay(string s, string t) {
      int ssz = s.size();
      int tsz = t.size();
      map <char, vector <int> > m;
      for(int i = 0; i < ssz; i++){
         m[s[i]].push_back(i);
      }
      int pre = -1;
      int ret = 1;
      for(int i = 0; i < tsz; i++){
         if(!m.count(t[i]))return -1;
         vector <int>& v = m[t[i]];
         vector <int> :: iterator it = upper_bound(v.begin(),
         v.end(), pre);
         if(it == v.end()){
            ret++;
            pre = v[0];
         }else{
            pre = *it;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.shortestWay("abc", "abcbc"));
}

入力

"abc"
"abcbc"

出力

2