题目地址：https://leetcode.com/problems/word-search/description/
题目描述
Given a 2D board and a word, find if the word exists in the grid.
Theword can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
题目大意
在一个二维表格里面，看看能不能连续的一笔画出word这个词。
解题方法
回溯法
还是经典的回溯法问题。这个题的回溯的起点可以是二维数组的任意位置。
回溯法的判定条件比较简单，需要注意的是把已经走过的路给改变了，不能再走了。python中通过swapcase()交换该字母的大小写即可行。
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
for y in xrange(len(board)):
for x in xrange(len(board[0])):
if self.exit(board, word, x, y, 0):
return True
return False
def exit(self, board, word, x, y, i):
if i == len(word):
return True
if x < 0 or x >= len(board[0]) or y < 0 or y >= len(board):
return False
if board[y][x] != word[i]:
return False
board[y][x] = board[y][x].swapcase()
isexit = self.exit(board, word, x + 1, y, i + 1) or self.exit(board, word, x, y + 1, i + 1) or self.exit(board, word, x - 1, y, i + 1) or self.exit(board, word, x, y - 1, i + 1)
board[y][x] = board[y][x].swapcase()
return isexit
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
使用C++的话，新开辟了一个visited数组，代表是否已经访问过了。总体代码不难。我使用了pair来保存位置，所以代码略显长了一些。
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if (word.size() == 0) return false;
const int M = board.size(), N = board[0].size();
vector<vector<bool>> visited(M, vector<bool>(N, false));
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j ++) {
if (dfs(board, word, 0, {i, j}, visited)) {
return true;
}
}
}
return false;
}
bool dfs(const vector<vector<char>>& board, const string& word, int start, pair<int, int> curpos, vector<vector<bool>>& visited) {
const int M = board.size(), N = board[0].size();
if (start == word.size()) return true;
if (curpos.first < 0 || curpos.first >= M || curpos.second < 0 || curpos.second >= N || visited[curpos.first][curpos.second] || word[start] != board[curpos.first][curpos.second])
return false;
visited[curpos.first][curpos.second] = true;
for (auto d : dirs) {
int nx = curpos.first + d.first;
int ny = curpos.second + d.second;
if (dfs(board, word, start + 1, {nx, ny}, visited))
return true;
}
visited[curpos.first][curpos.second] = false;
return false;
}
private:
vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发