Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Weird DFS solution in Clear category for On the same path by martin_b
from typing import Iterable, List, Tuple, Union, Set
Node = Union[int, str]
Tree = Tuple[Node, List['Tree']]
ThreeState = Union[bool, None]
def dfs(tree: Tree, items: Set[Node]) -> ThreeState:
not_found = None
# is it the required node
if tree[0] in items:
items -= {tree[0]}
if not items:
# found the second item of the pair
return True
# found the first item from the pair, now search only the subtree
not_found = False
# depth first search of the tree
for subtree in tree[1]:
result = dfs(subtree, items)
if result != None:
# either found both items (True) or only one in the subtree (False)
return result
return not_found
def on_same_path(tree: Tree, pairs: List[Tuple[Node, Node]]) -> Iterable[bool]:
return [bool(dfs(tree, set(p))) for p in pairs]
Dec. 29, 2019
Comments:
