โปรแกรมหาเลข Upside-down Numbers ความยาว n ใน Python

ปัญหา

หาเลข upside-down numbers ความยาว n - เลขที่อ่านเหมือนเดิมเมื่อหมุน 180 องศา

ตัวอย่าง: n=2 → ['11', '69', '88', '96']

คู่ตัวเลขที่หมุนได้

วิธีแก้: Recursive Generation

สร้างจากกลางออกไป (build from middle) โดยเพิ่มคู่ตัวเลขที่สองข้าง

อัลกอริทึม

1. ฟังก์ชัน middle(x) สร้างกลางของความยาว x
2. Base case: x=0 → [""], x=1 → ["0", "1", "8"]
3. Recursive: สำหรับแต่ละ middle string เพิ่มคู่ (0,0), (1,1), (6,9), (8,8), (9,6) ที่สองข้าง
4. ห้ามนำหน้าด้วย 0 (leading zero) → ตรวจสอบ x != n
5. เรียงลำดับผลลัพธ์สุดท้าย

โค้ด Python

class Solution:
    def solve(self, n):
        if not n:
            return []
        
        def middle(x):
            if x == 0:
                return [""]
            if x == 1:
                return ["0", "1", "8"]
            
            ret = []
            mid = middle(x - 2)
            for m in mid:
                if x != n:  # ไม่นำหน้าด้วย 0
                    ret.append("0" + m + "0")
                ret.append("1" + m + "1")
                ret.append("6" + m + "9")
                ret.append("8" + m + "8")
                ret.append("9" + m + "6")
            return ret
        
        return sorted(middle(n))

# ทดสอบ
ob = Solution()
print(ob.solve(1))  # ['0', '1', '8']
print(ob.solve(2))  # ['11', '69', '88', '96']
print(ob.solve(3))  # ['101', '111', '181', '609', '619', '689', '808', '818', '888', '906', '916', '986']

ความซับซ้อน

• Time: O(5^(n/2)) - exponential แต่ n มักเล็ก
• Space: O(5^(n/2)) สำหรับเก็บผลลัพธ์

การประยุกต์

Upside-down numbers ใช้ในปริศนา captcha, steganography, และ recreational mathematics