Khả năng xếp chữ cái từ ô gạch trong Python

Giả sử có tập ô gạch, mỗi ô có một chữ cái tiles[i]. Tìm số lượng chuỗi không rỗng có thể tạo. Nếu đầu vào "AAB", kết quả 8. Các chuỗi: "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Để giải quyết, ta làm theo các bước −

• Định nghĩa dfs(count)
• sum := 0
• với i từ 1 đến 26
  • nếu count[i] = 0, tiếp tục vòng lặp
  • giảm count[i] 1, tăng sum 1
  • sum := sum + dfs(count)
  • tăng count[i] 1
• trả về sum
• phương thức chính:
  • tạo mảng count kích thước 26, điền 0
  • với mỗi phần tử i trong tiles
    • tăng count[ord(i) - ord('A') + 1] 1
  • trả về dfs(count)

Xem triển khai sau −

Ví dụ

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"))

Đầu vào

"AAB"

Kết quả

8