Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2022-11-05 17:43:54
212. Word Search II
Word Search I 的加強版本,之前是給你一個字 word 讓你檢查矩陣裡面是否存在
該單字,現在是給你大於一個的 word。
Example:
https://assets.leetcode.com/uploads/2020/11/07/search1.jpg
Input: board =
[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],
words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
法一 回溯法 TLE
思路:
1.先建立一個map,記錄所有單字(a~z)是以哪些座標開頭。
2.利用回溯法遍歷 words 進 board 裡面找每個 word,如果該座標為起點找到時就提早
跳出迴圈,我們利用「#」字元來表示棋盤的位置已經被走訪過(避免回頭找)。
3.測資到倒數第二個位置的時候吃TLE。
Java Code:
作者: amsmsk (449)   2022-11-05 17:45:00
大師
作者: Jaka (Jaka)   2022-11-05 17:46:00
大師
作者: pandix (麵包屌)   2022-11-05 17:46:00
大師
作者: ririoshi (角落住民)   2022-11-05 17:47:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com