[LeetCode] 1079. Letter Tile Possibilities

1079. Letter Tile Possibilities

위 예시처럼 AAB 가 주어진다면 만들 수 있는 모든 경우를 따지면 된다.

조합은 AB, BA 를 같은 경우로 보고 순열은 AB, BA 를 다른 경우로 본다.

우선 조합으로 경우를 따진 뒤 그 경우마다 순열을 만들면 된다.

[A, B, AA, AB, AAB] 에 대해 각각 순열을 구하면 답을 구할 수 있다.

A → A

B → B

AA → AA

AB → AB, BA

AAB → AAB, ABA, BAA

하지만 우리는 만들 수 있는 문자열을 따지는 것 이기 때문에 index 0 에 있는 A 와 index 1 에 있는 A 를 같게 봐야한다.

8 번째 줄이나 10 번째 줄을 set 으로 받아 처음부터 중복을 지워도 되긴 하지만 그러기보다

마지막 연산 후 answer 를 set 으로 바꿔 중복을 지우면 조금이라도 빠르게 할 수 있다.

---

import itertools


class Solution:
	def numTilePossibilities(self, tiles: str) -> int:
		answer = []
		for i in range(1, len(tiles) + 1):
			_set = itertools.combinations(tiles, i)
			for j in _set:
				answer += itertools.permutations(j)

		return len(set(answer))


test = Solution()
tiles = 'JDNSJEK'
print(test.numTilePossibilities(tiles))