[Mock] Random 23

1079. Letter Tile Possibilities

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.

My Answer 1: Accepted (Runtime: 124 ms - 49.52% / Memory Usage: 17.4 MB - 38.39%)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def func(s, comb):
            self.comb.add(comb)
            
            if len(s) == 0:
                return
            
            for i in range(len(s)):
                func(s[:i]+s[i+1:], comb+s[i])
        
        self.comb = set()
        func(tiles, "")
        
        self.comb = list(self.comb)
        
        return len(self.comb) - 1

組み合わせが完了するたびにself.combを入れる""の空の文字列の組み合わせも含まれているので、全長-1 return

1042. Flower Planting With No Adjacent

You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. In each garden, you want to plant one of 4 types of flowers.
All gardens have at most 3 paths coming into or leaving it.
Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.
Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

My Answer 1: Accepted (Runtime: 476 ms - 36.34% / Memory Usage: 21.4 MB - 29.07%)

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        dic = {i+1:[] for i in range(n)}
        for i in range(len(paths)):
            dic[paths[i][0]].append(paths[i][1])
            dic[paths[i][1]].append(paths[i][0])
        
        ans = [0]*(n)
        
        for i in range(n):
            ans[i] = 1
            while ans[i] in dic[i+1]:
                ans[i] += 1
            for j in range(len(dic[i+1])):
                if i+1 in dic[dic[i+1][j]]:
                    dic[dic[i+1][j]].remove(i+1)
                    dic[dic[i+1][j]].append(ans[i])
        
        return ans

まず各園と隣接園をdicに保管する
定員1 ~ n、順次ans値を1に初期化
現在のansの値が隣接する庭にある場合、1つ増加するごとに、隣接しない数値が検索されます.
数値が確定した場合、庭に関連付けられた庭のdicの値が更新されます.
=>現在の値ではなくansに置き換えます.

Solution 1: Accepted (Runtime: 420 ms - 91.23% / Memory Usage: 21 MB - 87.22%)

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        res = [0] * n
        G = [[] for i in range(n)]
        for x, y in paths:
            G[x - 1].append(y - 1)
            G[y - 1].append(x - 1)
        for i in range(n):
            res[i] = ({1, 2, 3, 4} - {res[j] for j in G[i]}).pop()
        return res

差は多くないが、もっと速くできる.Gに隣の庭を置きます.
結果値は4種類の花です.{1, 2, 3, 4}から隣接値を減算し、値をポップアップするだけです.