題目連結(jié)：
題目意譯：
你被給定一個(gè)代表著公車(chē)路線(xiàn)的陣列 routes，其中 routes[i] 為第 i 臺(tái)公車(chē)會(huì)一直重複行駛的路線(xiàn)。
例如說(shuō)，如果 routes[0] = [1, 5, 7]，這代表著第 0 臺(tái)公車(chē)將以序列 1 → 5 → 7 → 1 → 5 → 7 → 1 → … 一直不斷地行駛下去。
你一開(kāi)始位於公車(chē)站牌 source（你最初不在任何公車(chē)上），而你想要到達(dá)公車(chē)站牌 target。你只能藉由公車(chē)在公車(chē)站牌之間移動(dòng)。
回傳從 source 到 target 最少所需要搭乘的公車(chē)數(shù)量。如果這不可能辦到，則回傳 -1。
限制：
1 ≦ routes.length ≦ 500.
1 ≦ routes[i].length ≦ 10 ^ 5
routes[i] 中的數(shù)值彼此相異。
sum(routes[i].length) ≦ 10 ^ 5
0 ≦ routes[i][j] < 10 ^ 6
0 ≦ source, target < 10 ^ 6
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： routes = [[1,2,7],[3,6,7]], source = 1, target = 6
輸出： 2
解釋?zhuān)?最佳策略為搭乘第一臺(tái)公車(chē)到 7 號(hào)站牌，接著搭乘第二臺(tái)到 6 號(hào)站牌。
範(fàn)例 2：
輸入： routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
輸出： -1
解題思維：
假設(shè)現(xiàn)在我們知道所有數(shù)對(duì) (i, j)，使得搭公車(chē) i 可以轉(zhuǎn)乘公車(chē) j（也就是說(shuō)，公車(chē) i 和 j 有相同的公車(chē)站牌），則此時(shí)實(shí)際上本題就變成類(lèi)似迷宮問(wèn)題（如這題）之題型。因此我們這時(shí)候只需要從站牌 source 進(jìn)行廣度優(yōu)先搜尋（Breadth First Search，BFS）一步一步地?cái)U(kuò)散即可以最少步數(shù)抵達(dá) target。
但問(wèn)題是我們不知道任何一對(duì) (i, j)，所以我們需要自行先把公車(chē)與公車(chē)互通（轉(zhuǎn)乘）的關(guān)係給建立出來(lái)。方式很簡(jiǎn)單：
用一個(gè)雜湊表（Hash Table）H 來(lái)記錄每一個(gè)站牌有哪些公車(chē)通行。因此我們掃過(guò)所有路線(xiàn)把 H 的內(nèi)容建立出來(lái)。
接著對(duì)於每一個(gè)站牌，把有通行於該站牌的所有公車(chē)彼此建立出互通的關(guān)係（即可以互相轉(zhuǎn)乘）。所有站牌掃完之後我們便知道所有上述所提及的數(shù)對(duì) (i, j)。
而這個(gè)步驟表面上看起來(lái)將會(huì)花上 O(|H| × n ^ 2)，其中 |H| 為 H 之大小（即站牌總數(shù)）、n 為 routes 之大小（即公車(chē)數(shù)）。但是由於題目給定了 sum(routes[i].length) ≦ 10 ^ 5 這個(gè)條件，所以單一公車(chē)路線(xiàn)有很多站牌則會(huì)限制其他公車(chē)與其互通的機(jī)會(huì)。
因此我們可以看到最糟的時(shí)間將會(huì)出現(xiàn)於 n 部公車(chē)的路線(xiàn)全部長(zhǎng)一模一樣的情況下。因此最糟時(shí)間複雜度為 O((10 ^ 5 ÷ n) × n ^ 2) = O(10 ^ 5 × n)，其實(shí)是還行的。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
