สตริงพจนานุกรมศัพท์ที่ k ของสตริงที่มีความยาวทั้งหมด n ใน C++

สมมติว่าเรามีสตริง เราจะเรียกว่าสตริงแห่งความสุขเมื่อประกอบด้วยตัวอักษร ['a', 'b', 'c'] เท่านั้น และ s[i] !=s[i + 1] สำหรับค่าทั้งหมดของ i ตั้งแต่ 1 ถึงความยาวของ s - 1 (ในที่นี้คือ 1-indexed)

ดังนั้น หากเรามีจำนวนเต็ม n และ k สองจำนวน ให้พิจารณารายการของสตริงที่มีความสุขทั้งหมดที่มีความยาว n ที่จัดเรียงตามลำดับศัพท์ เราต้องหาสตริงที่ k ของรายการนี้หรือส่งคืนสตริงว่างหากมีความยาวน้อยกว่า k สตริงที่มีความสุข n

ดังนั้น หากอินพุตเป็น n =3 และ k =9 เอาต์พุตจะเป็น "cab" มี Happy string ต่างกัน 12 ตัว ได้แก่ ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] อันที่ 9 คือ "cab"

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

• กำหนดอาร์เรย์ ret

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้เวลา s, l เริ่มต้นด้วย 1,

• ถ้า l เท่ากับ x แล้ว −

  • ใส่ s ต่อท้าย ret

  • กลับ

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

  • ถ้าองค์ประกอบสุดท้ายของ s ไม่เท่ากับ c[i] แล้ว −

    • แก้(s + c[i], l + 1)

• จากวิธีหลัก ให้ทำดังนี้ −

• x :=น

• ถ้า n เท่ากับ 0 แล้ว −

  • คืนค่าสตริงว่าง

• แก้("a")

• แก้("b")

• แก้("c")

• จัดเรียงอาร์เรย์ ret

• return (ถ้า k> ขนาดของ ret แล้วสตริงว่าง มิฉะนั้น ret[k - 1])

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
struct Cmp{
   bool operator()(string& a, string& b) {
      return !(a < b);
   }
};
char c[3] = {'a', 'b', 'c'};
class Solution {
public:
   vector<string> ret;
   int x;
   void solve(string s, int l = 1){
      if (l == x) {
         ret.push_back(s);
         return;
      }
      for (int i = 0; i < 3; i++) {
         if (s.back() != c[i]) {
            solve(s + c[i], l + 1);
         }
      }
   }
   string getHappyString(int n, int k){
      x = n;
      if (n == 0)
         return "";
      solve("a");
      solve("b");
      solve("c");
      sort(ret.begin(), ret.end());
      return k > ret.size() ? "" : ret[k - 1];
   }
};
main(){
   Solution ob;
   cout << (ob.getHappyString(3,9));
}

อินพุต

3,9

ผลลัพธ์

cab