資訊專欄INFORMATION COLUMN
摘要：當(dāng)遞歸到第次時(shí)，被調(diào)用了次。說明整個(gè)已經(jīng)被找到，返回?；氐胶瘮?shù)，遍歷整個(gè)數(shù)組，當(dāng)函數(shù)返回時(shí)，才返回否則在循環(huán)結(jié)束之后返回。
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.
ExampleGiven board =
[ "ABCE", "SFCS", "ADEE" ]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
建立helper函數(shù)，當(dāng)board[i][j]和word的第一個(gè)字符相等，將board[i][j]置為非字母的其它字符，防止這個(gè)元素再一次被調(diào)用，然后遞歸調(diào)用helper函數(shù)判斷board[i][j]的上下左右相鄰的字符是否和word的下一個(gè)字符相等并將結(jié)果存入res，再把board[i][j]置回原來的字符（可能和word.charAt(0)相同的字符在board[][]中有多種情況，而此解并非正解，故還原數(shù)組在main函數(shù)里繼續(xù)循環(huán)），然后遞歸返回res到上一層helper函數(shù)。
當(dāng)遞歸到第word.length次時(shí)，helper被調(diào)用了word.length+1次。說明整個(gè)word已經(jīng)被找到，返回true。
回到main函數(shù)，遍歷整個(gè)board數(shù)組，當(dāng)helper函數(shù)返回true時(shí)，才返回true；否則在循環(huán)結(jié)束之后返回false。
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65783.html
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...
摘要：使用，利用其按層次操作的性質(zhì)，可以得到最優(yōu)解。這樣可以保證這一層被完全遍歷。每次循環(huán)取出的元素存為新的字符串。一旦找到和相同的字符串，就返回轉(zhuǎn)換序列長(zhǎng)度操作層數(shù)，即。 Problem Given two words (start and end), and a dictionary, find the length of shortest transformation sequence...
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...
摘要：兩個(gè)循環(huán)遍歷整個(gè)矩陣，出現(xiàn)則將其周圍相鄰的全部標(biāo)記為，用子函數(shù)遞歸標(biāo)記。注意里每次遞歸都要判斷邊界。寫一個(gè)的，寫熟練。 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...
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) ...
閱讀 927·2021-09-09 09:32
閱讀 2904·2021-09-02 10:20
閱讀 2721·2021-07-23 11:24
閱讀 839·2019-08-30 15:54
閱讀 3645·2019-08-30 15:54
閱讀 1355·2019-08-30 11:02
閱讀 2860·2019-08-26 17:40
閱讀 1139·2019-08-26 13:55
