Số Strobogrammatic độ dài n (Strobogrammatic Number II) trong C++

Một số Strobogrammatic là số có hình dáng không thay đổi khi xoay 180 độ. Các cặp chữ số hợp lệ: (0,0), (1,1), (8,8), (6,9), (9,6). Nhiệm vụ: tìm tất cả các số Strobogrammatic có độ dài n.

Ví dụ

Đầu vào: n = 2
Đầu ra: ["11","69","88","96"] (Lưu ý: "00" không hợp lệ vì số không dẫn đầu bằng 0).

Thuật toán xây dựng đệ quy

1. Khởi tạo danh sách kết quả ret:
   • Nếu n lẻ: ret = {"0", "1", "8"} (các chữ số đối xứng tâm).
   • Nếu n chẵn: ret = {""} (chuỗi rỗng làm tâm).
2. Lặp cho đến khi độ dài đạt n (mỗi lần tăng 2):
   • Với mỗi chuỗi s trong ret, xây dựng chuỗi mới bằng cách thêm cặp chữ số ở hai đầu.
   • Nếu đang xây dựng lớp ngoài cùng (n > 3), cho phép cặp ("0","0").
   • Luôn thêm các cặp: ("1","1"), ("8","8"), ("6","9"), ("9","6").
3. Trả về ret.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        vector<string> ret;
        if (n & 1) {
            ret = {"0", "1", "8"};
        } else {
            ret = {""};
        }
        for (; n > 1; n -= 2) {
            vector<string> temp;
            for (const string& s : ret) {
                if (n > 3) temp.push_back("0" + s + "0");
                temp.push_back("1" + s + "1");
                temp.push_back("8" + s + "8");
                temp.push_back("6" + s + "9");
                temp.push_back("9" + s + "6");
            }
            ret = move(temp);
        }
        return ret;
    }
};

Độ phức tạp

• Thời gian & Không gian: O(5^(n/2)) - số lượng kết quả tăng theo cấp số nhân.

Kết quả kiểm thử

Đầu vào: 3
Đầu ra: [101, 808, 609, 906, 111, 818, 619, 916, 181, 888, 689, 986]