22.12.30 Today’s Leetcode

797. All Paths From Source to Target (medium)

DAG에서 경로를 찾는 문제. DFS를 이용하여 해결!

class Solution:

    def dfs(self, graph, res, path):
        n = len(graph)
        current = path[-1]
        if current == n - 1:
            res.append(path)
        for node in graph[current]:
            if node not in path:
                new_path = path[:]
                new_path.append(node)
                self.dfs(graph, res, new_path)

    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        # DAG find all possible paths from node 0 to n - 1 and return them in any order
        res = []
        self.dfs(graph, res, [0])
        return res        

1346. Check If N and Its Double Exist (Easy)

set을 이용하여 문제풀이. 두 배이거나 두 배가 되는 숫자를 temp에서 찾는 경우 True 반환

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        n = len(arr)
        temp = set()
        for num in arr:
            if (num * 2) in temp or (num / 2) in temp:
                return True
            temp.add(num)
        return False

1079. Letter Tile Possibilities (Medium)

python의 permutation method를 이용하자.

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        res = 0
        for i in range(1, len(tiles) + 1):
            res += len(set(itertools.permutations(tiles, i)))
        return res

이건 permutation을 떠올리기전에 했던 잡생각들.. 중복되는걸 체크하지못해서 막혔었음. 그러니까 {'A': 1, 'B': 0} 가 recursion 도중에 두번 나타나는데 이걸 distinct 하게 생각하는게 아니라 동일하게 생각해야되서, 일단 여기서 막혔고 그래서 permutation을 이용해서 구현하는 방식으로 방향을 바꾸었음.

class Solution:

    def fact(self, num):
        if num <= 0:
            return 1
        return num * self.fact(num - 1)

    # def comb(self, a, b):
    #     return self.fact(a) / (self.fact(a - b) * self.fact(b))

    def comb(self, counter):
        total, denom = 0, 1
        for value in counter.values():
            total += value
            denom *= self.fact(value)
        return self.fact(total) // denom

    def help(self, counter, length):
        print (counter)
        total, res, denom = 0, 0, 1
        res += self.comb(counter)
        for key in counter.keys():
            if counter[key] > 0 and length >= 2:
                counter[key] -= 1
                res += self.help(counter, length - 1)
                counter[key] += 1
        return res

    def numTilePossibilities(self, tiles: str) -> int:
        counter = collections.Counter(tiles)
        return self.help(counter, len(tiles))

JAVA에서 backtracking을 이용하여 구현한 버전. 내가 구현한 것이랑 비슷하긴 한데, swapping과 문자열이 짧은 순으로 올라간다는 점이 다르다.

class Solution {
    private Set<String> set;

    public int numTilePossibilities(String tiles) {
        set = new HashSet<>();
        backtrack(tiles.toCharArray(), 0);
        return set.size();
    }

    private void backtrack(char[] chars, int i) {
        if (i >= 1) {
            set.add(String.valueOf(Arrays.copyOf(chars, i)));
        }
        
        if (i == chars.length) return;

        for (int j = i; j < chars.length; j++) {
            swap(chars, i, j);
            backtrack(chars, i + 1);
            swap(chars, i, j);
        }
    }

    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}