Frog Position After T Seconds LeetCode solution in JavaScript

1
/**
2
 * @param {number} n
3
 * @param {number[][]} edges
4
 * @param {number} t
5
 * @param {number} target
6
 * @return {number}
7
 */
8
function dfs(n, map, t, target, visited, prop) {
9
  // edge case1: if run out of steps, cannot find target
10
  if (t === 0 && n !== target) return 0;
11
  // edge case2: if run out of steps, but found target
12
  if (t === 0 && n === target) return prop;
13

14
  visited.add(n);
15
  // get unvisited children/neighbors
16
  const validChildren = [];
17
  (map[n] ?? []).forEach((child) => {
18
    if (!visited.has(child)) validChildren.push(child);
19
  });
20
  // edge case3, if still more steps to use, but no more children to move,
21
  // if already at the targeted node, should just return
22
  if (n === target && t > 0 && !validChildren.length) return prop;
23
  // edge case4, if still more steps to use and no more children to move,
24
  // but current node is not target node, cannot find target, return 0
25
  if (n !== target && t > 0 && !validChildren.length) return 0;
26

27
  // go to next valid child/neighbor
28
  for (let i = 0; i < validChildren.length; i++) {
29
    if (visited.has(validChildren[i])) continue;
30
    let result = dfs(
31
      validChildren[i],
32
      map,
33
      t - 1,
34
      target,
35
      visited,
36
      prop * (1 / validChildren.length)
37
    );
38
    if (result !== 0) return result;
39
  }
40

41
  return 0;
42
}
43

44
var frogPosition = function (n, edges, t, target) {
45
  const map = new Array(n + 1);
46
  // make bidirectional edge map
47
  edges.forEach((item) => {
48
    if (!map[item[0]]) map[item[0]] = [];
49
    if (!map[item[1]]) map[item[1]] = [];
50
    map[item[0]].push(item[1]);
51
    map[item[1]].push(item[0]);
52
  });
53

54
  return dfs(1, map, t, target, new Set(), 1);
55
};