[LeetCode] 1079. Letter Tile Possibilities (Python)

 

 

난이도: Medium

문제 설명

---

You have n  tiles, where each tile has one letter tiles[i] printed on it.

 

Return the number of possible non-empty sequences of letters you can make using the letters printed on those tiles.

 

문제 예제

---

Example 1:

Input: tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: tiles = "AAABBC"
Output: 188

Example 3:

Input: tiles = "V"
Output: 1

 

제한 사항

---

• 1 <= tiles.length <= 7
• tiles consists of uppercase English letters.

 

✏️ Solution(솔루션)

---

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        answer = 0
        sequence = set()
        n = len(tiles)
        visited = [False] * n

        def backtracking(now, tiles, n, visited):
            nonlocal answer
            if now:
                sequence.add(''.join(now))
                answer += 1
            
            for i in range(n):
                if not visited[i]:
                    visited[i] = True
                    now.append(tiles[i])

                    if ''.join(now) not in sequence:
                        backtracking(now, tiles, n, visited)

                    now.pop()
                    visited[i] = False
        
        backtracking([], tiles, n, visited)

        return answer

 

이 문제 역시 backtracking으로 풀었다.

 

tiles에 요소들을 방문 처리 해가면서 만들 수 있는 모든 sequence를 찾아 answer에 +1씩 해주었다.

 

이 때, 중복된 sequence가 생길 수 있기 때문에 set을 통해 중복처리 해주었다.

 

즉, 만약 set에 현재 sequence가 이미 있다면 갯수를 센 sequence이기 때문에 넘어갔다.

 

backtracking 연산이 끝나면 마지막에 answer를 return하여 정답을 맞출 수 있었다.

 

---

문제: 1079. Letter Tile Possibilities

 

깃허브: github

algorithmPractice/LeetCode/1160-letter-tile-possibilities at main · laewonJeong/algorithmPractice