สตริง Happy ลำดับที่ K แบบ Lexicographical ใน C++

สตริงจะเป็น "happy" ถ้าประกอบด้วย 'a','b','c' เท่านั้น และไม่มีตัวติดกันซ้ำ (s[i] ≠ s[i+1]) กำหนด n, k หา happy string ความยาว n ลำดับที่ k เรียง lexicographical

ตัวอย่าง: n=3, k=9 → "cab" (มีทั้งหมด 12 สตริง: aba, abc, aca, acb, bab, bac, bca, bcb, cab, cac, cba, cbc)

วิธีแก้ปัญหา (Backtracking)

1. DFS สร้าง happy strings ทั้งหมด:
   • เริ่มจาก 'a','b','c'
   • ต่อตัวอักษรที่ต่างจากตัวสุดท้าย
   • ครบความยาว n เก็บใน vector
2. เรียง vector
3. คืนค่าตัวที่ k-1 (ถ้ามี)

ตัวอย่างโค้ด C++

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

int main(){ 
    Solution ob; 
    cout << (ob.getHappyString(3,9)); 
}

ข้อมูลนำเข้า

3,9

ผลลัพธ์

cab