前往
大廳
主題

LeetCode - 1496. Path Crossing 解題心得

Not In My Back Yard | 2021-12-02 00:00:01 | 巴幣 0 | 人氣 342

題目連結:


題目意譯:
給定一個字串 path,其中 path[i] = 'N' 、 'S' 、 'E' 或是 'W',依序代表著往北、南、東或西移動一單位。你開始於一個二維座標平面之原點 (0, 0) 並遵循 path 描述之路徑。

回傳真(True)如果路徑在任意時刻有與其自身交錯,即如果在任何時間點你位於先前已抵達過的位置。反之,回傳假(False)。

限制:
1 ≦ path.length ≦ 10 ^ 4
path[i] 只會是 'N' 、 'S' 、 'E' 或 'W'。



範例測資:
範例 1:
輸入: path = "NES"
輸出: false
解釋: 注意該路徑不會經過任一個點超過一次以上。

範例 2:
輸入: path = "NESWW"
輸出: true
解釋: 注意路徑經過了原點兩次。


解題思維:
模擬行走的路徑,並利用雜湊表(Hash Table)將每個經過的點(包含原點)儲存起來。如果當前抵達的點已經存在於表中,則代表路徑會與自己相交,因此回傳真;反之,如果路徑模擬完後沒有發現相交處,則回傳假。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作