Python 中的字母拼块可能性
pythonserver side programmingprogramming
假设我们有一组拼块，每个拼块上印有一个字母 tiles[i]。求出我们可以制作的非空字母序列的数量。因此，如果输入是"AAB"，则输出将为 8。因为序列是"A"、"B"、"AA"、"AB"、"BA"、"AAB"、"ABA"、"BAA"
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个 dfs()，它将取 count
- sum := 0
- 对于 i 在 1 到 26 的范围内
- 如果 count[i] = 0，则进行下一次迭代，而不检查其余部分
- 将 count[i] 减少 1，并将 sum 增加1
- sum := sum + dfs(count)
- 将 count[i] 增加 1
- 返回 sum
- 实际方法将类似于 −
- 创建一个大小为 26 的 count 数组，并用 0 填充
- 对于 tiles 中的每个元素 i
- 将 count[i – ‘A’ + 1] 增加 1
- 返回 dfs(count)
让我们看看下面的实现以便更好地理解 −
示例
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
