Can You Walk It
Each entry of links is a pair [a, b]: a path between places a and b that can be walked in both directions. walk is a list of places that someone claims to have visited, in this order, always going straight from one place to the next.
Return True if every step of the walk follows a path, and False otherwise. A walk that names a single place is always possible. Staying in place is not a step: two equal places in a row need a path from the place to itself, and there are none.
Example 1
links [[0,1],[1,2]]
walk [0,1,2,1]
returns true
The steps 0 to 1, 1 to 2 and 2 back to 1 all follow paths.
Example 2
links [[0,1],[1,2]]
walk [0,2]
returns false
There is no path between 0 and 2.
Example 3
links [[0,1]]
walk [5]
returns true
Nothing to check.
Constraints
- places are numbered
0to11 0 <= len(links) <= 30, and a path joins two different places1 <= len(walk) <= 20
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Count the LinksBeginner
- Dead EndsBeginner
- Degree of Every NodeBeginner
- Everyone Knows EveryoneBeginner
- Friends in CommonBeginner
- Is There a RoadBeginner
- Next DoorBeginner
- No HandshakeBeginner