Wiki Page Links II
You are given getLinkedPages(uri), which fetches a wiki page and returns the URIs it links to. Return a shortest sequence of pages from start to target, both included, or an empty list if target cannot be reached. From a page to itself the path is just [start].
// A -> B, A -> C, B -> D, C -> D
clickPath("A", "D", getLinkedPages) -> ["A", "B", "D"] (or ["A", "C", "D"])Any shortest path is accepted. Fetching is expensive: the harness fails a run that fetches the same page twice, and its fetcher returns an empty list for unknown pages.
Hints
Hint 1
Same BFS as for the click count, but remember how each page was first reached: a map from page to the page it was discovered from.
Hint 2
When the target is discovered, follow the predecessor map back to the start and reverse. Storing a whole path per queue entry costs O(V · path) memory instead of O(V).