Giả sử chúng ta có một tập hợp các ô, trong đó mỗi ô có một ô chữ cái [i] được in trên đó. Tìm số lượng các dãy chữ cái không trống có thể có mà chúng ta có thể thực hiện. Vì vậy, nếu đầu vào là “AAB”, thì đầu ra sẽ là 8. Vì các chuỗi là “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một dfs (), sẽ được tính
- sum:=0
- cho tôi trong phạm vi từ 1 đến 26
- nếu count [i] =0, thì hãy chuyển sang lần lặp tiếp theo mà không cần kiểm tra phần còn lại
- giảm số lượng [i] đi 1 và tăng tổng số 1
- sum:=sum + dfs (đếm)
- tăng số lượng [i] lên 1
- trả về tổng
- phương pháp thực tế sẽ như thế nào -
- tạo một mảng đếm có kích thước 26 và điền vào mảng này bằng 0
- cho mỗi phần tử i trong các ô
- tăng số lượng [i - ‘A’ + 1] lên 1
- trả về dfs (số lượng)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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"
Đầu ra
8