Skip to content

Latest commit

 

History

History
executable file
·
308 lines (295 loc) · 11.2 KB

79. Word Search.md

File metadata and controls

executable file
·
308 lines (295 loc) · 11.2 KB

79. Word Search

Question:

Given a 2D board and a word, find if the word exists in the grid.

The word 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.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Thinking:

  • Method:
    • 回溯，无法通过，超时
class Solution {
    public boolean exist(char[][] board, String word) {
        if(null == board || board.length == 0 || word == null) return false;
        int height = board.length; int width = board[0].length;
        if(height * width < word.length()) return false;
        char c = word.charAt(0);
        boolean[][] used = new boolean[height][width];
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if(board[i][j] == c){
                    used[i][j] = true;
                    if(backtrace(board, i, j, 1, word, height, width, used))
                        return true;
                    used[i][j] = false;
                }
            }
        }
        return false;
    }
    public static boolean backtrace(char[][] board, int x, int y, int index, String word, int height, int width, boolean[][] used){
        if(index == word.length())
            return true;
        else{
            char c = word.charAt(index);
            List<Integer> option = valid(board, x, y, c, used);
            if(option.size() == 0) return false;
            else{
                boolean temp = false;
                for(Integer opt : option){
                    switch(opt){
                        case 0:
                            used[x - 1][y] = true;
                            temp |= backtrace(board, x - 1, y, index + 1, word, height, width, used);
                            used[x - 1][y] = false;
                            break;
                        case 1:
                            used[x][y - 1] = true;
                            temp |= backtrace(board, x, y - 1, index + 1, word, height, width, used);
                            used[x][y - 1] = false;
                            break;
                        case 2:
                            used[x + 1][y] = true;
                            temp |= backtrace(board, x + 1, y, index + 1, word, height, width, used);
                            used[x + 1][y] = false;
                            break;
                        case 3:
                            used[x][y + 1] = true;
                            temp |= backtrace(board, x, y + 1, index + 1, word, height, width, used);
                            used[x][y + 1] = false;
                            break;
                    }
                }
                return temp;
            }
        }
    }
    private static List<Integer> valid(char[][] board, int x, int y, char c, boolean[][] used){ // -1: invalid, 0: up, 1: left, 2: down, 3: right
        List<Integer> result = new ArrayList<>();
        if(x > 0) if(!used[x - 1][y] && board[x - 1][y] == c) result.add(0);
        if(y > 0) if(!used[x][y - 1] && board[x][y - 1] == c) result.add(1);
        if(x < board.length - 1) if(!used[x + 1][y] && board[x + 1][y] == c) result.add(2);
        if(y < board[0].length - 1) if(!used[x][y + 1] && board[x][y + 1] == c) result.add(3);
        return result;
    }
}
  • Method2:
    • 仍然是回溯，但是减少了不必要的判断操作
class Solution {
    public boolean exist(char[][] board, String word) {
        if(null == board || board.length == 0 || word == null) return false;
        int height = board.length; int width = board[0].length;
        if(height * width < word.length()) return false;
        char c = word.charAt(0);
        boolean[][] used = new boolean[height][width];
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if(board[i][j] == c){
                    used[i][j] = true;
                    if(backtrace(board, i - 1, j, 1, word, height, width, used)||
                      backtrace(board, i + 1, j, 1, word, height, width, used) ||
                      backtrace(board, i, j - 1, 1, word, height, width, used) ||
                      backtrace(board, i, j + 1, 1, word, height, width, used))
                        return true;
                    used[i][j] = false;
                }
            }
        }
        return false;
    }
    public static boolean backtrace(char[][] board, int x, int y, int index, String word, int height, int width, boolean[][] used){
        if(index == word.length())
            return true;
        else{
            char c = word.charAt(index);
            if(valid(board, x, y, c, used)){
                used[x][y] = true;
                boolean result = backtrace(board, x - 1, y, index + 1, word, height, width, used) ||
                    backtrace(board, x, y - 1, index + 1, word, height, width, used) ||
                    backtrace(board, x + 1, y, index + 1, word, height, width, used) ||
                    backtrace(board, x, y + 1, index + 1, word, height, width, used);
                if(result) return true;
                used[x][y] = false;
            }
            return false;
        }
    }
    private static boolean valid(char[][] board, int x, int y, char c, boolean[][] used){
        if(x >= 0 && x < board.length && y >= 0 && y < board[0].length)
            if(!used[x][y] && board[x][y] == c) return true;
        return false;
    }
}

二刷

二刷直接就写了DFS的方法，但是一开始写的办法还是会出现RTL，所以稍微修改了一下写出了AC的结果。

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || board[0].length == 0 || word == null) return false;
        int height = board.length, width = board[0].length;
        boolean[][] used = new boolean[height][width];
        char[] wordArr = word.toCharArray();
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if(board[i][j] == wordArr[0]){
                    used[i][j] = true;
                    if(exist(board, wordArr, 1, i, j, used)) return true;
                    used[i][j] = false;
                }
            }
        }
        return false;
    }    
    private boolean exist(char[][] board, char[] word, int index, int row, int col, boolean[][] used){
        if(index == word.length) return true;
        else{
            char c = word[index];
            int tempRow = 0, tempCol = 0;
            for(int d = 0; d < 4; d++){
                tempRow = row + dir[d][0]; tempCol = col + dir[d][1];
                if(tempRow >= 0 && tempRow < board.length && tempCol >= 0 && tempCol < board[0].length && !used[tempRow][tempCol]){
                    if(c == board[tempRow][tempCol]){
                        used[tempRow][tempCol] = true;
                        if(exist(board, word, index + 1, tempRow, tempCol, used)) return true;
                        used[tempRow][tempCol] = false;
                    }
                }
            }
            return false;
        }
    }
}

Third time

  • Method 1: Search + dfs 
    class Solution {
    public boolean exist(char[][] board, String word) {
        if(word == null || word.length() == 0) return true;
        int height = board.length, width = board[0].length;
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if(board[i][j] == word.charAt(0))
                    if(dfs(board, word, i, j, 0, new boolean[height][width])) return true;
            }
        }
        return false;
    }      
    private boolean dfs(char[][] board, String word, int i, int j, int index, boolean[][] visited){
        if(index == word.length() - 1)  return true;
        visited[i][j] = true;
        int tempRow = 0, tempCol = 0;
        for(int d = 0; d < 4; d++){
            tempRow = i + dir[d][0];
            tempCol = j + dir[d][1];
            if(tempRow >= 0 && tempRow < visited.length && tempCol >= 0 && tempCol < visited[0].length && board[tempRow][tempCol] == word.charAt(index + 1) &&  !visited[tempRow][tempCol]){
                if(dfs(board, word, tempRow, tempCol, index + 1, visited)) return true;
            }
        }
        visited[i][j] = false;
        return false;
    }
}

Amazon Session

  • Method 1: dfs 
     class Solution {
 	private static final int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
 	private char[][] board;
 	private int height, width;
 	private String word;
 	public boolean exist(char[][] board, String word) {
 		if(board == null || board.length == 0 || board[0].length == 0) return false;
 		this.board = board;
 		this.height = board.length;
 		this.width = board[0].length;
 		this.word = word;
 		for(int i = 0; i < height; i++){
 			for(int j = 0; j < width; j++){
 				if(word.charAt(0) == board[i][j]){
 					Set<Integer> visited = new HashSet<>();
 					visited.add(i * width + j);
 					if(dfs(i, j, visited, 0)) return true;
 				}
 			}
 		}
 		return false;
 	}
 	private boolean dfs(int x, int y, Set<Integer> visited, int index){
 		if(index == word.length() - 1) return true;
 		int tx = 0, ty = 0;
 		for(int d = 0; d < 4; d++){
 			tx = x + dir[d][0];
 			ty = y + dir[d][1];
 			if(tx >= 0 && tx < height && ty >= 0 && ty < width && !visited.contains(tx * width + ty) && board[tx][ty] == word.charAt(index + 1)){
 				visited.add(tx * width + ty);
 				if(dfs(tx, ty, visited, index + 1)) return true;
 				visited.remove(tx * width + ty);
 			}
 		}
 		return false;
 	}
 }

C++ version

  • Method 1: dfs
class Solution {
private:
    static int dir[4][2];
    vector<vector<char>> board_;
    int height, width;
    bool dfs(const string& word, int index, int i, int j, vector<vector<int>>& visited){
        if(index == word.length()) return true;
        int tx = 0, ty = 0;
        for(int d = 0; d < 4; ++d){
            tx = i + Solution::dir[d][0];
            ty = j + Solution::dir[d][1];
            if(tx >= 0 && tx < height && ty >= 0 && ty < width && !visited[tx][ty] && word[index] == board_[tx][ty]){
                visited[tx][ty] = true;
                if(dfs(word, index + 1, tx, ty, visited)) return true;
                visited[tx][ty] = false;
            }
        }
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        this->height = board.size();
        this->width = board[0].size();
        board_ = move(board);
        vector<vector<int>> visited(height, vector<int>(width, false)); 
        for(int i = 0; i < height; ++i){
            for(int j = 0; j < width; ++j){
                if(word[0] == board_[i][j]){
                    visited[i][j] = true;
                    if(dfs(word, 1, i, j, visited)) return true;
                    visited[i][j] = false;
                }
            }
        }
        return false;
    }
};
int Solution::dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
static auto speedup=[](){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return nullptr;
}();