Attraction Route Without Reusing Trails
WhatNot● HardFULLTIMENEW GRADPHONE SCREENProblem statement
An attraction park is an undirected graph. Vertices are locations and each trail is an undirected edge that may be traversed at most once.
Find a route that starts at start, ends at end, and visits every vertex in desiredAttractions at least once. Other vertices may be visited, and vertices may repeat when reached through different unused trails.
Return the lexicographically smallest valid vertex sequence. Compare two routes at their first differing vertex, and prefer the shorter route when one is a prefix of the other. Return an empty array when no valid route exists.
Function
findAttractionRoute(n: int, trails: int[][], desiredAttractions: int[], start: int, end: int) → int[]Examples
Example 1
n = 5trails = [[0,1],[1,2],[2,4],[1,3],[3,4],[1,4]]desiredAttractions = [2,3]start = 0end = 4return = [0,1,2,4,1,3,4]The route uses each listed trail at most once and visits both requested attractions. It is lexicographically smaller than alternatives beginning 0,1,3.
Example 2
n = 4trails = [[0,1],[1,2],[2,3]]desiredAttractions = [1,2]start = 0end = 3return = [0,1,2,3]The only start-to-end route visits both desired vertices.
Example 3
n = 4trails = [[0,1],[2,3]]desiredAttractions = [2]start = 0end = 3return = []The graph components are disconnected.
Constraints
1 <= n <= 12.0 <= trails.length <= 18.- Each trail contains two distinct vertices in
[0, n - 1]; parallel trails are allowed and are distinct edges. desiredAttractions.length <= n.start,end, and every desired attraction are valid vertices.