题目描述
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1：
输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]
示例 2：
输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]
提示：
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j]是一个小写英文字母1 <= words.length <= 3 * 1041 <= words[i].length <= 10words[i]由小写英文字母组成words中的所有字符串互不相同
算法
本题采用的方法就是回溯法
我一直不怎么擅长回溯法，索性这道题还是做出来了。
我的方法是因为要查找的单词是不重复的，所以可以将他们全部存入一个map中，然后每当我们查找到一个单词，就从这个map中删掉他，这样既可以减少我们后面查找的时间，也可以避免重复查找。
然后开始查找map中的单词，从board的每一个位置开始，获取board中当前位置的字符，然后与map中每一个单词的第index个字符进行比较，如果遇到相同的，就判断index是不是这个单词的最后一个字符的位置，如果是最后一个字符，那么就从map中删除这个单词，如果不是最后一个字符，那么就将这个单词加入到下一轮查找中。
如果比较的结果是不相同的，那么就跳过这个单词了，不再做处理（这就是回溯法中的剪枝），如果进入下一轮比较的单词数量为0，那么就退出函数了。
然后进行下一轮查找，其实就是深度查找吧，感觉差不多，向上下左右四个方向查找，前提是这个方向的下一个字符是没有被查找过的。
代码
go
// 因为go中的所有向函数传递参数都是值传递的，在传递切片的时候，其实也是值传递的，只不过拷贝的是切片的类似于地址这种东西，在go中切片没有像c++中那样直接深拷贝vector的值传递，所以我们需要真正的值传递slice的时候，需要自己在传递之前对slice进行拷贝。
func findWords(board [][]byte, words []string) []string {
res := []string{}
if len(board) == 0 {
return res
}
if len(board[0]) == 0 {
return res
}
wordsMap := make(map[string]struct{})
for _, word := range words {
wordsMap[word] = struct{}{}
}
var recursion func(i, j int, travl [][]int, leftWords []string, index int)
recursion = func(i, j int, travl [][]int, leftWords []string, index int) {
if len(wordsMap) == 0 {
return
}
if len(leftWords) == 0 {
return
}
tmpWords := []string{}
for _, word := range leftWords {
if byte(word[index]) == board[i][j] {
if index == len(word)-1 {
res = append(res, word)
delete(wordsMap, word)
} else {
tmpWords = append(tmpWords, word)
}
}
}
travl[i][j] = 1
index++
// 往上下左右走
// 上
if i-1 >= 0 && travl[i-1][j] == 0 {
topTravl := make([][]int, len(travl))
for t := 0; t < len(travl); t++ {
topTravl[t] = make([]int, len(travl[0]))
copy(topTravl[t], travl[t])
}
topWords := make([]string, 0)
// copy(topWords, tmpWords)
for _, word := range tmpWords {
if _, ok := wordsMap[word]; ok {
topWords = append(topWords, word)
}
}
recursion(i-1, j, topTravl, topWords, index)
}
// 下
if i+1 < len(travl) && travl[i+1][j] == 0 {
downTravl := make([][]int, len(travl))
for t := 0; t < len(travl); t++ {
downTravl[t] = make([]int, len(travl[0]))
copy(downTravl[t], travl[t])
}
downWords := make([]string, 0)
// copy(downWords, tmpWords)
for _, word := range tmpWords {
if _, ok := wordsMap[word]; ok {
downWords = append(downWords, word)
}
}
recursion(i+1, j, downTravl, downWords, index)
}
// 左
if j-1 >= 0 && travl[i][j-1] == 0 {
leftTravl := make([][]int, len(travl))
for t := 0; t < len(travl); t++ {
leftTravl[t] = make([]int, len(travl[0]))
copy(leftTravl[t], travl[t])
}
leftWords := make([]string, 0)
// copy(leftWords, tmpWords)
for _, word := range tmpWords {
if _, ok := wordsMap[word]; ok {
leftWords = append(leftWords, word)
}
}
recursion(i, j-1, leftTravl, leftWords, index)
}
// 右
if j+1 < len(travl[0]) && travl[i][j+1] == 0 {
rightTravl := make([][]int, len(travl))
for t := 0; t < len(travl); t++ {
rightTravl[t] = make([]int, len(travl[0]))
copy(rightTravl[t], travl[t])
}
rightWords := make([]string, 0)
// copy(rightWords, tmpWords)
for _, word := range tmpWords {
if _, ok := wordsMap[word]; ok {
rightWords = append(rightWords, word)
}
}
recursion(i, j+1, rightTravl, rightWords, index)
}
}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
// 创建是否遍历二维网格
isTraval := make([][]int, len(board))
for k := 0; k < len(board); k++ {
isTraval[k] = make([]int, len(board[0]))
}
tmpWords := make([]string, 0)
// copy(tmpWords, words)
// outIndex := 0
// for word := range wordsMap {
// tmpWords[outIndex] = word
// outIndex++
// }
for _, word := range words {
if _, ok := wordsMap[word]; ok {
tmpWords = append(tmpWords, word)
}
}
recursion(i, j, isTraval, tmpWords, 0)
}
}
// wordsMap := make(map[string]bool)
// for _, word := range res {
// wordsMap[word] = true
// }
// res = []string{}
// for word := range wordsMap {
// res = append(res, word)
// }
return res
}
c++
// c++中vector不需要自己进行值传递从而深拷贝，所以代码看起来会简单一点。但是值得注意的地方是从vector中erase元素的时候，他是自动指向了下一个元素的迭代器位置，所以当调用了erase后，不需要显式的iter++，但是在map中执行erase后，还是指向当前的位置的迭代器，所以需要显示执行iter++并且需要先指向后面，也就是这样erase: erase(iter++)，然后在没有执行erase的时候，需要显式iter++
class Solution {
public:
vector<string> res;
map<string,bool> wordsMap;
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
if(board.size()==0){
return res;
}
if(board[0].size()==0){
return res;
}
for(auto it=words.cbegin();it!=words.cend();it++){
wordsMap[*it]=true;
}
vector<vector<int>> travl(board.size(),vector<int>(board[0].size(),0));
for(size_t i=0;i<board.size();i++){
for(size_t j=0;j<board[0].size();j++){
vector<string> tmpWords;
for(auto word=words.cbegin();word!=words.cend();word++){
if(wordsMap.find(*word)!=wordsMap.end()){
// map中存在元素
tmpWords.push_back(*word);
}
}
recursion(i,j,board,travl,tmpWords,0);
}
}
return res;
}
void recursion(int i,int j,const vector<vector<char>> &board, vector<vector<int>> travl,vector<string> leftWords,int index){
if(wordsMap.size()==0){
return;
}
if(leftWords.size()==0){
return;
}
vector<string> tmpWords;
for(auto lit=leftWords.cbegin();lit!=leftWords.cend();lit++){
if(board[i][j]==(*lit)[index]){
if(index==(*lit).size()-1){
res.push_back(*lit);
wordsMap.erase(*lit);
}else{
tmpWords.push_back(*lit);
}
}
}
index++;
travl[i][j]=1;
// 上下左右
// 上
if(i-1>=0&&travl[i-1][j]==0){
for(auto it=tmpWords.begin();it!=tmpWords.end();){
if(wordsMap.find(*it)==wordsMap.end()){
tmpWords.erase(it);
}else{
it++;
}
}
recursion(i-1,j,board,travl,tmpWords,index);
}
// 下
if(i+1<board.size()&&travl[i+1][j]==0){
for(auto it=tmpWords.begin();it!=tmpWords.end();){
if(wordsMap.find(*it)==wordsMap.end()){
tmpWords.erase(it);
}else{
it++;
}
}
recursion(i+1,j,board,travl,tmpWords,index);
}
// 左
if(j-1>=0&&travl[i][j-1]==0){
for(auto it=tmpWords.begin();it!=tmpWords.end();){
if(wordsMap.find(*it)==wordsMap.end()){
tmpWords.erase(it);
}else{
it++;
}
}
recursion(i,j-1,board,travl,tmpWords,index);
}
// 右
if(j+1<board[0].size()&&travl[i][j+1]==0){
for(auto it=tmpWords.begin();it!=tmpWords.end();){
if(wordsMap.find(*it)==wordsMap.end()){
tmpWords.erase(it);
}else{
it++;
}
}
recursion(i,j+1,board,travl,tmpWords,index);
}
}
};