单词搜索

解题思路：先把给定的board转换成二维矩阵，再二重循环找到与单词首字母相同的坐标，然后广度优先遍历矩阵。值得注意的是，遍历矩阵时，把当前坐标位置的字母置空，避免重复经过。遍历退出时再还原。从上下左右任意一个方向搜索到完整的一个单词时，就直接返回即可

import java.util.*;
public class Solution {
    public boolean exist (String[] board, String word) {
        char[][] mat = new char[board.length][board[0].length()];
        for(int i = 0; i < board.length; ++i) {
            mat[i] = board[i].toCharArray();
        }
        return exist(mat, word);
    }
    public boolean exist(char[][] board, String word) {
        for(int i = 0; i < board.length; ++i) {
            for(int j = 0; j < board[i].length; ++j) {
                if(board[i][j] == word.charAt(0)) {
                    if(func(board, word, 0, i , j)) return true;
                }
            }
        }
        return false;
    }
    public boolean func(char[][] board, String word, int index, int i, int j) {
        if(index >= word.length()) return true;
        if(i >= 0 && i < board.length && j >= 0 && j < board[i].length) {
            if(board[i][j] == word.charAt(index)) {
                board[i][j] = ' ';
                boolean res =  func(board, word, index + 1, i + 1, j) || 
                func(board, word, index + 1, i , j + 1) ||
                func(board, word, index + 1, i - 1, j) ||
                func(board, word, index + 1, i, j - 1);
                board[i][j] = word.charAt(index);
                return res;
            }
        }
        return false;
    }
}

package main
import _"fmt"
import "strings"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param board string字符串一维数组 
 * @param word string字符串 
 * @return bool布尔型
*/
func exist( board []string ,  word string ) bool {
    m,n:=len(board),len(board[0])
    mat:=[][]string{}
    for _,s:=range board{
        mat=append(mat,strings.Split(s,""))
    }
    var flag bool
    var dfs func(int,int,string)
    dfs=func(i,j int,word string){
        if flag||i<0||i>=m||j<0||j>=n||mat[i][j]==""||mat[i][j]!=string(word[0]){
            return
        }
        tmp:=mat[i][j]
        mat[i][j]=""
        word=word[1:]
        if len(word)==0{
            flag=true
            return
        }
        dfs(i+1,j,word)
        dfs(i-1,j,word)
        dfs(i,j+1,word)
        dfs(i,j-1,word)
        mat[i][j]=tmp
    }
    for i:=0;i<m;i++{
        for j:=0;j<n;j++{
            if mat[i][j]==string(word[0]){
                dfs(i,j,word)
                if flag{
                    return true
                }
            }
        }
    }
    return false
}

思路：命里有时终须有，命里无时莫强求。

import java.util.*;
public class Solution {
    public boolean exist(String[] strs, String word) {
        char[][] board = new char[strs.length][strs[0].length()];
        for (int i = 0; i < strs.length; i++) board[i] = strs[i].toCharArray();
        for (int i = 0; i < strs.length; i++) {
            for (int j = 0; j < strs[0].length(); j++) {
                if (dfs(board, word.toCharArray(), i, j, 0)) return true;
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if (i >= board.length || i = board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if (k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}