79. 單詞搜索：
給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)字符串單詞 word 。如果 word 存在于網(wǎng)格中，返回 true ；否則，返回 false 。
單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。
樣例 1：
輸入：
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
輸出：
true
樣例 2：
輸入：
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
輸出：
true
樣例 3：
文章來源：http://www.zghlxwxcb.cn/news/detail-700023.html
輸入：
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
輸出：
false
提示：
- m == board.length
- n = board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board 和 word 僅由大小寫英文字母組成
進(jìn)階：
- 你可以使用搜索剪枝的技術(shù)來優(yōu)化解決方案，使其在
board更大的情況下可以更快解決問題？
分析：
- 面對(duì)這道算法題目，二當(dāng)家的再次陷入了沉思。
- 需要嘗試所有的可能，遍歷是不可少的，使用循環(huán)或者遞歸，遞歸是首選，因?yàn)楸容^容易實(shí)現(xiàn)，深度優(yōu)先，回溯，遞歸套娃大法好。
- 需要遍歷每一個(gè)元素，然后開始從每個(gè)位置使用遞歸套娃大法，分別向上，下，左，右四個(gè)方向進(jìn)行遞歸，重復(fù)操作，直到匹配成功，或者匹配失敗就回溯嘗試其他，需要注意的是不走重復(fù)的位置，所以需要一個(gè)結(jié)構(gòu)標(biāo)記已經(jīng)走過的位置，使用和原二維字符網(wǎng)格相同大小的結(jié)構(gòu)比較容易，空間上應(yīng)該還可以優(yōu)化，但是沒有深究，因?yàn)榭臻g上并沒有浪費(fèi)，如果做優(yōu)化，肯定是以犧牲效率為代價(jià)，所謂時(shí)間換空間，我不要換。
題解：
rust：
impl Solution {
pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
fn check(board: &Vec<Vec<char>>, word: &Vec<char>, idx: usize, visited: &mut Vec<Vec<bool>>, r: usize, c: usize) -> bool {
if r >= visited.len() || c >= visited[0].len() || visited[r][c] || board[r][c] != word[idx] {
return false;
}
if idx == word.len() - 1 {
// 完全匹配
return true;
}
visited[r][c] = true;
// 上下左右遞歸套娃大法
if check(board, word, idx + 1, visited, r - 1, c)
|| check(board, word, idx + 1, visited, r + 1, c)
|| check(board, word, idx + 1, visited, r, c - 1)
|| check(board, word, idx + 1, visited, r, c + 1)
{
return true;
}
visited[r][c] = false;
return false;
}
let word = word.chars().collect::<Vec<_>>();
let mut visited = vec![vec![false; board[0].len()]; board.len()];
for r in 0..board.len() {
for c in 0..board[0].len() {
if check(&board, &word, 0, &mut visited, r, c) {
return true;
}
}
}
return false;
}
}
go：
func exist(board [][]byte, word string) bool {
visited := make([][]bool, len(board))
for i := range visited {
visited[i] = make([]bool, len(board[0]))
}
var check func(idx, r, c int) bool
check = func(idx, r, c int) bool {
if r < 0 || r >= len(board) || c < 0 || c >= len(board[0]) || visited[r][c] || board[r][c] != word[idx] {
return false
}
if idx == len(word)-1 {
// 完全匹配
return true
}
visited[r][c] = true
// 上下左右遞歸套娃大法
if check(idx+1, r-1, c) || check(idx+1, r+1, c) || check(idx+1, r, c-1) || check(idx+1, r, c+1) {
return true
}
visited[r][c] = false
return false
}
for r, row := range board {
for c := range row {
if check(0, r, c) {
return true
}
}
}
return false
}
c++：
class Solution {
private:
bool check(vector<vector<char>>& board, string& word, int idx, vector<vector<bool>>& visited, int r, int c) {
if (r < 0 || r >= visited.size() || c < 0 || c >= visited[0].size() || visited[r][c] || board[r][c] != word[idx]) {
return false;
}
if (idx == word.size() - 1) {
// 完全匹配
return true;
}
visited[r][c] = true;
// 上下左右遞歸套娃大法
if (check(board, word, idx + 1, visited, r - 1, c)
|| check(board, word, idx + 1, visited, r + 1, c)
|| check(board, word, idx + 1, visited, r, c - 1)
|| check(board, word, idx + 1, visited, r, c + 1)) {
return true;
}
visited[r][c] = false;
return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
for (int r = 0; r < board.size(); ++r) {
for (int c = 0; c < board[0].size(); ++c) {
if (check(board, word, 0, visited, r, c)) {
return true;
}
}
}
return false;
}
};
python：
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def check(idx: int, r: int, c: int) -> bool:
if r < 0 or r >= len(board) or c < 0 or c >= len(board[0]) or visited[r][c] or board[r][c] != word[idx]:
return False
if idx == len(word) - 1:
return True
visited[r][c] = True
if check(idx + 1, r - 1, c) or check(idx + 1, r + 1, c) or check(idx + 1, r, c - 1) or check(idx + 1, r, c + 1):
return True
visited[r][c] = False
return False
visited = [[False] * len(board[0]) for _ in range(len(board))]
for r in range(len(board)):
for c in range(len(board[0])):
if check(0, r, c):
return True
return False
java：
class Solution {
public boolean exist(char[][] board, String word) {
boolean[][] visited = new boolean[board.length][board[0].length];
for (int r = 0; r < board.length; ++r) {
for (int c = 0; c < board[0].length; ++c) {
if (check(board, word, 0, visited, r, c)) {
return true;
}
}
}
return false;
}
private boolean check(char[][] board, String word, int idx, boolean[][] visited, int r, int c) {
if (r < 0 || r >= visited.length || c < 0 || c >= visited[0].length || visited[r][c] || board[r][c] != word.charAt(idx)) {
return false;
}
if (idx == word.length() - 1) {
// 完全匹配
return true;
}
visited[r][c] = true;
// 上下左右遞歸套娃大法
if (check(board, word, idx + 1, visited, r - 1, c)
|| check(board, word, idx + 1, visited, r + 1, c)
|| check(board, word, idx + 1, visited, r, c - 1)
|| check(board, word, idx + 1, visited, r, c + 1)) {
return true;
}
visited[r][c] = false;
return false;
}
}
非常感謝你閱讀本文~
歡迎【點(diǎn)贊】【收藏】【評(píng)論】三連走一波~
放棄不難，但堅(jiān)持一定很酷~
希望我們大家都能每天進(jìn)步一點(diǎn)點(diǎn)~
本文由 二當(dāng)家的白帽子：https://le-yi.blog.csdn.net/ 博客原創(chuàng)~文章來源地址http://www.zghlxwxcb.cn/news/detail-700023.html
到了這里，關(guān)于算法leetcode｜79. 單詞搜索（rust重拳出擊）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
