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