[LeetCode/LintCode] Word Search

Aceyclee 发布于2019-08-14 15:28 / 2046人阅读

摘要：当递归到第次时，被调用了次。说明整个已经被找到，返回。回到函数，遍历整个数组，当函数返回时，才返回否则在循环结束之后返回。

Problem

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

Given board =

[
  "ABCE",
  "SFCS",
  "ADEE"
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Note

建立helper函数，当board[i][j]和word的第一个字符相等，将board[i][j]置为非字母的其它字符，防止这个元素再一次被调用，然后递归调用helper函数判断board[i][j]的上下左右相邻的字符是否和word的下一个字符相等并将结果存入res，再把board[i][j]置回原来的字符（可能和word.charAt(0)相同的字符在board[][]中有多种情况，而此解并非正解，故还原数组在main函数里继续循环），然后递归返回res到上一层helper函数。
当递归到第word.length次时，helper被调用了word.length+1次。说明整个word已经被找到，返回true。
回到main函数，遍历整个board数组，当helper函数返回true时，才返回true；否则在循环结束之后返回false。

Solution update 2018-9

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) return word == null || word.length() == 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0) && helper(board, i, j, 0, word)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean helper(char[][] board, int i, int j, int index, String word) {
        if (index == word.length()) return true;
        if (i >= 0 && i < board.length && 
            j >= 0 && j < board[0].length 
            && board[i][j] == word.charAt(index)) {
            board[i][j] = "#";
            boolean res = helper(board, i+1, j, index+1, word) ||
                helper(board, i-1, j, index+1, word) ||
                helper(board, i, j+1, index+1, word) ||
                helper(board, i, j-1, index+1, word);
            board[i][j] = word.charAt(index);
            return res;
        }
        return false;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65783.html

[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 评论0 收藏0
[LeetCode/LintCode] Word Ladder

摘要：使用，利用其按层次操作的性质，可以得到最优解。这样可以保证这一层被完全遍历。每次循环取出的元素存为新的字符串。一旦找到和相同的字符串，就返回转换序列长度操作层数，即。 Problem Given two words (start and end), and a dictionary, find the length of shortest transformation sequence...

张金宝 2019-08-14 15:27 评论0 收藏0
[LeetCode/LintCode] Sentence Similarity

Problem Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar. For example, great acting skills a...

dreamtecher 2019-08-16 12:44 评论0 收藏0
[LeetCode/LintCode] Number of Islands [DFS]

摘要：两个循环遍历整个矩阵，出现则将其周围相邻的全部标记为，用子函数递归标记。注意里每次递归都要判断边界。写一个的，写熟练。 Number of Islands Problem Given a boolean/char 2D matrix, find the number of islands. 0 is represented as the sea, 1 is represented as...

Fourierr 2019-08-14 15:15 评论0 收藏0
[LeetCode/LintCode] Is Subsequence

Problem Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) ...

terasum 2019-08-19 11:05 评论0 收藏0