Visit Desired Attractions Without Reusing a Trail
Duolingoâ—Ź HardINTERNPHONE SCREENProblem statement
You are planning a camping walk from Parking Lot to Campsite. Each row of trails is an undirected trail between two attractions. Different rows are different physical trails, so parallel trails between the same two attractions remain independently usable.
Return whether there is a walk that:
- starts at
Parking Lot; - ends at
Campsite; - visits every name in
desiredAttractionsat least once; and - uses each individual trail row at most once.
An attraction may be visited more than once. Reaching Campsite early does not force the walk to stop; it may leave and return as long as unused trails remain.
Function
canVisitAllAttractions(trails: String[][], desiredAttractions: String[]) → booleanExamples
Example 1
trails = [["Beaver Dam","Frozen Ocean"],["Beaver Dam","Frozen Ocean"],["Parking Lot","Beaver Dam"],["Parking Lot","Liberty Lake"],["Beaver Dam","Campsite"],["Eel Weir","Campsite"],["Eel Weir","Campsite"]]desiredAttractions = ["Frozen Ocean"]return = trueOne valid walk is Parking Lot → Beaver Dam → Frozen Ocean → Beaver Dam → Campsite. The two Beaver Dam–Frozen Ocean rows are distinct trails.
Example 2
trails = [["Beaver Dam","Frozen Ocean"],["Beaver Dam","Frozen Ocean"],["Parking Lot","Beaver Dam"],["Parking Lot","Liberty Lake"],["Beaver Dam","Campsite"],["Eel Weir","Campsite"],["Eel Weir","Campsite"]]desiredAttractions = ["Liberty Lake","Beaver Dam"]return = falseThe only trail incident to Liberty Lake would need to be used both entering and leaving, which is forbidden.
Example 3
trails = [["Beaver Dam","Frozen Ocean"],["Beaver Dam","Frozen Ocean"],["Parking Lot","Beaver Dam"],["Parking Lot","Liberty Lake"],["Beaver Dam","Campsite"],["Eel Weir","Campsite"],["Eel Weir","Campsite"]]desiredAttractions = ["Eel Weir"]return = trueA valid walk is Parking Lot → Beaver Dam → Campsite → Eel Weir → Campsite, using the two parallel Eel Weir–Campsite trails once each.
Constraints
1 <= trails.length <= 20.- Every trail row contains exactly two non-empty attraction names.
- Parallel trail rows are allowed and have separate identities.
0 <= desiredAttractions.length <= 15; duplicates in this list do not require multiple visits.- Every desired attraction appears in at least one trail row.