Letter Tile Possibilities
MediumHash TableStringBacktrackingCounting
문제 설명
주어진 문자열 tiles
에서 각 문자는 하나의 타일을 나타냅니다.
주어진 타일을 사용하여 만들 수 있는 모든 가능한 문자열의 개수를 반환하는 문제입니다.
문제 풀이
Map
을 사용하여, 주어진 타일(문자)의 개수를 저장합니다.- 백트래킹을 사용하여서, 각 타일을 한 번씩 선택하여 가능한 문자열을 만들어 나갑니다.
Map
을 순회합니다.- 타일의 개수가 0인 경우, 다음 타일을 탐색합니다.
- 타일의 개수가 0이 아닌 경우, 사용한 타일의 개수를 줄이고, 재귀 호출하여 다음 타일을 계속해서 선택합니다. 원래 상태로 되돌리고 계속 다음 타일을 탐색합니다.
function numTilePossibilities(tiles: string): number {
const tileCounter = new Map<string, number>();
for (const tile of tiles) {
tileCounter.set(tile, (tileCounter.get(tile) ?? 0) + 1);
}
let totalCount = 0;
function backtrack(): void {
for (const [tile, tileCount] of tileCounter) {
if (tileCount === 0) {
continue;
}
totalCount += 1;
tileCounter.set(tile, tileCount - 1);
backtrack();
tileCounter.set(tile, tileCount);
}
}
backtrack();
return totalCount;
}
복잡도
- 시간 복잡도:
- 공간 복잡도: