Leetcode 1377. Frog Position After T Seconds

📅2023-07-14🧐106

Leetcode 1377. Frog Position After T Seconds

The question clearly told us the frog cannot jump to a visited vertex, which means if it is on a path and if the path doesn't have a branch, it cannot go back! So we even don't need to backtrack on this problem.

After we collected all the possibilities from a vertex and the neighbors, we could calculate the result.

from collections import defaultdict

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        graph = defaultdict(list)

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        def dfs(node, t):
            count = len(graph[node]) - 1 # remove pointer to current node
            if node == 1:
                # the root is a exception
                count += 1

            # while no more choice or timeout
            if t == 0 or count == 0:
                return 1 if target == node else 0

            # check probability from children (neighbors)
            for nei in graph[node]:
                if nei in seen:
                    continue
                seen.add(nei)
                res = dfs(nei, t - 1)
                if res != 0:
                    # return the probability if the way we choose is correct
                    return res / count

            return 0

        seen = set([1])
        ans = dfs(1, t)
        return ans