แยกสตริงที่ต่อกันใน C ++

สมมติว่าเรามีรายการสตริง เราสามารถเชื่อมสตริงเหล่านี้เข้าด้วยกันเป็นลูป โดยที่แต่ละสตริงเราสามารถเลือกที่จะย้อนกลับได้หรือไม่ ในบรรดาลูปที่เป็นไปได้ทั้งหมด เราต้องหาสตริงที่ใหญ่ที่สุดตามพจนานุกรมหลังจากตัดลูป ซึ่งจะทำให้สตริงที่วนซ้ำเป็นสตริงปกติ โดยเฉพาะอย่างยิ่ง เพื่อหาสตริงที่ใหญ่ที่สุด lexicographically เราต้องพบกับสองขั้นตอน -

เชื่อมสตริงทั้งหมดเข้าเป็นวงเดียว โดยเราสามารถย้อนกลับบางสตริงหรือไม่ก็ได้ และเชื่อมต่อในลำดับเดียวกันตามที่กำหนด

ตัดและสร้างจุดตัดหนึ่งจุดในที่ใดก็ได้ของลูป ซึ่งจะทำให้สตริงที่วนซ้ำกลายเป็นจุดปกติโดยเริ่มจากอักขระที่จุดตัด และงานคือการหาพจนานุกรมที่ใหญ่ที่สุดในบรรดาสตริงปกติที่เป็นไปได้ทั้งหมด

ดังนั้น หากอินพุตเป็นเหมือน "abc", "xyz" ผลลัพธ์จะเป็น "zyxcba" เนื่องจากเราสามารถรับสตริงที่วนซ้ำได้ เช่น "-abcxyz-", "-abczyx-", "-cbaxyz-", " -cbazyx-” โดยที่ '-' ใช้เพื่อแสดงสถานะ loop สตริงคำตอบมาจากลูปที่สี่ซึ่งเราสามารถตัดจากอักขระกลาง 'a' และรับ "zyxcba"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้ idx, array strs, rev

• อุณหภูมิ :=strs[idx]

• ถ้า rev ไม่ใช่ศูนย์ ดังนั้น −

  • ย้อนกลับอุณหภูมิอาร์เรย์

• str1 :=สตริงว่าง

• str2 :=สตริงว่าง

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน

  • str1 :=str1 + strs[i]

• สำหรับการเริ่มต้น i :=idx + 1 เมื่อ i <ขนาดของ strs อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • str2 :=str2 + strs[i]

• สำหรับการเริ่มต้น k :=0 เมื่อ k

  • newOne :=สตริงย่อยของ temp จากดัชนี k ไปยัง end concatenate str2 concatenate str1 เชื่อมสตริงย่อยของ temp จากดัชนี (0 ถึง k-1)

  • ถ้า ret ว่างเปล่าหรือ ret

    • ret :=newOne

• กำหนดฟังก์ชัน findMax() ซึ่งจะใช้อาร์เรย์ strs

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของ strs ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • อุณหภูมิ :=strs[i]

  • ย้อนกลับอุณหภูมิอาร์เรย์

  • strs[i] :=(ถ้า strs[i]> temp แล้ว strs[i] มิฉะนั้น temp)

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ret :=สตริงว่าง

• findMax(strs)

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของ strs ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • แก้(i, strs, เท็จ)

  • แก้(i, strs, จริง)

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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