각 타일에 하나의 글자 타일[i]이 인쇄되어 있는 타일 세트가 있다고 가정합니다. 우리가 만들 수 있는 비어 있지 않은 문자 시퀀스의 수를 찾으십시오. 따라서 입력이 "AAB"이면 출력은 8이 됩니다. 시퀀스는 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 카운트가 필요한 하나의 dfs() 정의
- 합계 :=0
- 1에서 26 사이의 i에 대해
- count[i] =0이면 나머지를 확인하지 않고 다음 반복으로 이동합니다.
- count[i]를 1로 줄이고 합계를 1로 늘립니다.
- 합계 :=합 + dfs(개수)
- count[i] 1 증가
- 반환 합계
- 실제 방법은 다음과 같습니다 -
- 크기가 26인 하나의 카운트 배열을 만들고 0으로 채웁니다.
- 타일의 각 요소 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