สมมติว่าเรามีชุดกระเบื้อง โดยแต่ละแผ่นมีแผ่นตัวอักษรหนึ่งตัว[i]พิมพ์อยู่ ค้นหาจำนวนลำดับตัวอักษรที่ไม่ว่างเปล่าที่เป็นไปได้ที่เราสามารถสร้างได้ ดังนั้นหากอินพุตคือ "AAB" เอาต์พุตจะเป็น 8 เนื่องจากลำดับคือ "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดหนึ่ง dfs() ที่จะนับ
- ผลรวม :=0
- สำหรับฉันอยู่ในช่วง 1 ถึง 26
- ถ้า count[i] =0 ให้ทำซ้ำต่อไปโดยไม่ต้องตรวจสอบส่วนที่เหลือ
- ลดจำนวน[i] 1 และเพิ่มผลรวม 1
- sum :=sum + dfs(นับ)
- เพิ่มจำนวน[i] ขึ้น 1
- ผลตอบแทน
- วิธีการจริงจะเป็นเช่น −
- สร้างอาร์เรย์การนับหนึ่งขนาด 26 และเติมด้วย 0
- สำหรับแต่ละองค์ประกอบ i ในไทล์
- เพิ่มจำนวน[i – ‘A’ + 1] ขึ้น 1
- ส่งคืน dfs(นับ)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object):
def numTilePossibilities(self, tiles):
count = [0 for i in range(27)]
for i in tiles:
count[ord(i)-ord('A')+1]+=1
return self.dfs(count)
def dfs(self,count):
summ = 0
for i in range(1,27):
if count[i]==0:
continue
count[i]-=1
summ+=1
summ+=self.dfs(count)
count[i]+=1
return summ
ob = Solution()
print(ob.numTilePossibilities("AAB")) อินพุต
"AAB"
ผลลัพธ์
8
