#815
Bus Routes
candidate master · 1495 · lc hard +32 · verified · 47.2% accepted · 4,672 likes · top 32%
Description
You are given an array routes representing bus lines, where routes[i] is the sequence of stops that bus i visits in an infinite loop.
- For example, if routes[0] = [1, 5, 7], bus 0 travels 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> ... forever.
Starting at bus stop source (you are not currently on any bus), you want to reach bus stop target. Travel between stops is only possible by bus.
Return the minimum number of buses you must board to travel from source to target. Return -1 if it is impossible.
Example 1:
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
Example 2:
Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1
Code
1
2
3