Tách chuỗi liên kết trong C ++

Giả sử chúng ta có một danh sách các chuỗi, chúng ta có thể nối các chuỗi này lại với nhau thành một vòng lặp, trong đó đối với mỗi chuỗi chúng ta có thể chọn đảo ngược nó hoặc không. Trong số tất cả các vòng lặp có thể có, chúng ta cần tìm chuỗi lớn nhất về mặt từ vựng sau khi cắt vòng lặp, điều này sẽ làm cho chuỗi được lặp thành một chuỗi thông thường. Cụ thể, để tìm chuỗi lớn nhất về mặt từ vựng, chúng ta cần trải qua hai giai đoạn -

Nối tất cả các chuỗi thành một vòng lặp, nơi chúng ta có thể đảo ngược một số chuỗi hoặc không và kết nối chúng theo thứ tự như đã cho.

Cắt và tạo một điểm cắt ở bất kỳ vị trí nào của vòng lặp, điều này sẽ làm cho chuỗi được lặp lại thành một chuỗi đều đặn bắt đầu từ ký tự tại điểm cắt. Và công việc là tìm chuỗi từ điển lớn nhất trong số tất cả các chuỗi thông thường có thể có.

Vì vậy, nếu đầu vào là "abc", "xyz", thì đầu ra sẽ là "zyxcba" vì chúng ta có thể nhận được chuỗi lặp như "-abcxyz-", "-abczyx-", "-cbaxyz-", " -cbazyx- ”, trong đó '-' được sử dụng để biểu thị trạng thái lặp lại. Chuỗi câu trả lời đến từ chuỗi lặp thứ tư, nơi chúng ta có thể cắt từ ký tự giữa 'a' và lấy" zyxcba ".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm giải quyết (), điều này sẽ lấy idx, mảng strs, rev,

• temp:=strs [idx]

• nếu rev ​​khác 0, thì -

  • đảo ngược nhiệt độ mảng

• str1:=chuỗi rỗng

• str2:=chuỗi trống

• để khởi tạo i:=0, khi tôi

  • str1:=str1 + strs [i]

• để khởi tạo i:=idx + 1, khi tôi

  • str2:=str2 + strs [i]

• để khởi tạo k:=0, khi k

  • newOne:=chuỗi con tạm thời từ chỉ số k đến kết thúc kết thúc str2 nối str1 nối chuỗi con tạm thời từ chỉ mục (0 đến k-1)

  • nếu ret trống hoặc ret

    • ret:=newOne

• Xác định một hàm findMax (), điều này sẽ lấy một chuỗi mảng,

• để khởi tạo i:=0, khi tôi

  • tạm thời:=strs [i]

  • đảo ngược nhiệt độ mảng

  • strs [i]:=(nếu strs [i]> tạm thời thì strs [i], nếu không thì tạm thời)

• Từ phương thức chính, hãy làm như sau -

• ret:=chuỗi trống

• findMax (strs)

• để khởi tạo i:=0, khi tôi

  • giải quyết (i, strs, false)

  • giải quyết (i, strs, true)

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

{"abc", "xyz"}

Đầu ra

zyxcba