[LeetCode/LintCode] Word Search

Aceyclee 發布于2019-08-14 15:28 / 2047人閱讀

摘要：當遞歸到第次時，被調用了次。說明整個已經被找到，返回。回到函數，遍歷整個數組，當函數返回時，才返回否則在循環結束之后返回。

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;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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