[LeetCdoe] 1079. Letter Tile Possibilities (Python)

Problem

 

Solution

permutation
backtracking DFS

중복 순열을 사용한 문제.

중복 허용, 순서 고려하여 모든 경우의수를 따져야하지만 만들어진 string이 중복되면안된다.

permutation을 사용하되 결과를 set에 담아서 저장하도록했다.

 

백트래킹을 사용했지만 시간복잡도에서 최악의 경우 많이 소요될 수 있다.

Code

import itertools

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:

        def generate(cur, used, result, r):
            if len(cur) == r:
                print(cur)
                result.add(''.join(cur))
                return
            
            for i in range(len(tiles)):
                if used[i]:
                    continue
                used[i]=True
                cur.append(tiles[i])
                generate(cur, used, result, r)
                used[i]=False
                cur.pop()

        if len(tiles) == 1:
            return 1

        result = set()
        for r in range(1, len(tiles)+1):
            used = [False] * len(tiles)
            generate([], used, result, r)

        return len(result)

 

Complexity

 

• 시간 복잡도: O(2^n) (중복 순열이 있을 경우 최대 경우)
• 공간 복잡도: O(n! + n) (순열을 저장하기 위한 공간)

 

 

backtracking 은 어려워..