C++で連結文字列を分割する

文字列のリストがあるとすると、これらの文字列を1つのループに連結できます。ここで、文字列ごとに、文字列を反転するかどうかを選択できます。考えられるすべてのループの中で、ループを切断した後、辞書式順序で最大の文字列を見つける必要があります。これにより、ループされた文字列が通常の文字列になります。具体的には、辞書式順序で最大の文字列を見つけるには、2つのフェーズを経験する必要があります-

すべての文字列を1つのループに連結します。ここで、一部の文字列を逆にするかどうかを指定して、指定されたのと同じ順序で接続できます。

ループの任意の場所でカットして1つのカットポイントを作成します。これにより、ループされた文字列が、カットポイントの文字から始まる通常の文字列になります。そして、その仕事は、考えられるすべての通常の文字列の中から辞書式順序で最大のものを見つけることです。

したがって、入力が「abc」、「xyz」の場合、「-abcxyz-」、「-abczyx-」、「-cbaxyz-」、「」のようなループ文字列を取得できるため、出力は「zyxcba」になります。 -cbazyx-」、ここで「-」はループ状態を表すために使用されます。応答文字列は4番目のループ文字列から取得され、中央の文字「a」から切り取って「zyxcba」を取得できます。

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

• 関数solve（）を定義します。これには、idx、array strs、rev、

  が必要です。

• temp：=strs [idx]

• revがゼロ以外の場合、-

  • アレイの温度を逆にします

• str1：=空の文字列

• str2：=空の文字列

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

  • str1：=str1 + strs [i]

• 初期化i：=idx + 1の場合、i

  • str2：=str2 + strs [i]

• 初期化k：=0の場合、k <温度のサイズの場合、更新（kを1増やします）、実行-

  • newOne：=インデックスkから終了までの一時のサブストリング連結str2連結str1インデックスからの一時のサブストリング（0からk-1）

  • retが空の場合またはret

    • ret：=newOne

• 関数findMax（）を定義します。これには、配列strsが必要です。

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

  • temp：=strs [i]

  • アレイの温度を逆にします

  • strs [i]：=（strs [i]> tempの場合、strs [i]、それ以外の場合はtemp）

• メインの方法から、次のようにします-

• ret：=空の文字列

• findMax（strs）

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

  • 解決（i、strs、false）

  • 解決（i、strs、true）

• retを返す

例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string ret;
   void solve(int idx, vector <string > strs, bool rev){
      string temp = strs[idx];
      if (rev)
         reverse(temp.begin(), temp.end());
      string str1 = "";
      string str2 = "";
      for (int i = 0; i < idx; i++)
         str1 += strs[i];
      for (int i = idx + 1; i < strs.size(); i++)
         str2 += strs[i];
      for (int k = 0; k < temp.size(); k++) {
         string newOne = temp.substr(k) + str2 + str1 + temp.substr(0, k);
         if (ret == "" || ret < newOne) {
            ret = newOne;
         }
      }
   }
   void findMax(vector<string>& strs){
      for (int i = 0; i < strs.size(); i++) {
         string temp = strs[i];
         reverse(temp.begin(), temp.end());
         strs[i] = strs[i] > temp ? strs[i] : temp;
      }
   }
   string splitLoopedString(vector& strs) {
      ret = "";
      findMax(strs);
      for (int i = 0; i < strs.size(); i++) {
         solve(i, strs, false);
         solve(i, strs, true);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"abc", "xyz"};
   cout << (ob.splitLoopedString(v));
}

入力

{"abc", "xyz"}

出力

zyxcba