โจทย์: กำหนดชุดกระเบื้องตัวอักษร tiles หาจำนวนลำดับ (sequences) ที่เป็นไปได้ทั้งหมด (ไม่ว่าง) โดยแต่ละกระเบื้องใช้ได้สูงสุด 1 ครั้งต่อลำดับ
ตัวอย่าง
Input: "AAB"
Output: 8 (ลำดับ: "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA")
อัลกอริทึม: DFS + Backtracking
- นับความถี่ตัวอักษรแต่ละตัว (26 ตัวอักษร)
- DFS: ลองวางตัวอักษรแต่ละตัวที่ยังเหลืออยู่ แล้วเรียกซ้ำ
- Backtracking: คืนค่าความถี่หลังเรียกซ้ำ
- นับทุกครั้งที่วางตัวอักษรสำเร็จ
ตัวอย่างโค้ด Python
class Solution(object):
def numTilePossibilities(self, tiles):
# นับความถี่ตัวอักษร (index 1-26 สำหรับ A-Z)
count = [0] * 27
for ch in tiles:
count[ord(ch) - ord('A') + 1] += 1
return self.dfs(count)
def dfs(self, count):
total = 0
for i in range(1, 27):
if count[i] == 0:
continue
# ใช้ตัวอักษรนี้
count[i] -= 1
total += 1 # นับลำดับที่เพิ่งสร้าง
total += self.dfs(count) # ขยายต่อ
count[i] += 1 # backtrack
return total
# ทดสอบ
ob = Solution()
print(ob.numTilePossibilities("AAB")) # Output: 8
ตัวอย่าง Input/Output
Input: "AAB" Output: 8
หมายเหตุ: โค้ดต้นฉบับมี bug เล็กน้อย (ใช้ range(27) แต่ index 0 ไม่ได้ใช้) โค้ดข้างต้นแก้ไขแล้ว ใช้ index 1-26 สำหรับ A-Z
