Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы LeetCodeВ 48-й статье давайте рассмотрим 79-й вопрос в LeetCode, поиск слов.
Официальная сложность этого вопроса — «Средняя», процент ответов — 34,5%, 3488 лайков и 170 отклонений. Только из этих данных,Этот вопрос высокого качества, и это немного сложнее, чем предыдущие вопросы. Лично я считаю проходной балл более сложным и содержательным показателем, чем официальные вопросы: от 10% до 20% можно считать сложными вопросами, а около 30% — сложными вопросами. 50% — это простой вопрос, поэтому, если вы видите заголовок с пометкой «Сложно», но показатель успешности составляет 50%, либо вопрос очень водянистый, либо данные очень водянистые, всегда есть немного водянистого.
смысл названия
Без лишних слов, давайте посмотрим на смысл вопроса:
Название этого вопроса очень интересно Учитывая двумерный массив символов и строку, нас просят судитьМожете ли вы найти путь в 2D-массиве, чтобы конкатенированная строка символов на этом пути была равна заданной строке?
Образец
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.
Например, первая строка ABCCED, мы можем найти такой путь в массиве:
отвечать
Я не знаю, что вы чувствуете, когда видите вопрос и этот пример.Если вы читали много вопросов и часто думали об этом, я думаю, не должно быть трудно обнаружить, что суть этого вопроса на самом деле такая же, каклабиринтэто то же самое.
Получившийся двумерный массив символов представляет собой лабиринт, и мы хотим найти «выход» из этого лабиринта. Но наша цель не в том, чтобы найти конец, а в том, чтобы найти путь, соответствующий смыслу вопроса. В задаче о прохождении лабиринта не каждую точку лабиринта можно пройти, а также в текущей задаче не каждая точка удовлетворяет требованиям строки. Хотя темы этих двух вопросов кажутся совершенно разными, основная суть одна и та же.
Вспомним, как должна решаться задача о прохождении лабиринта?
Ответ уже должен быть очень определенным, конечно, этоалгоритм поиска. Нам нужно исследовать пространство, где может существовать решение, чтобы найти существующее решение, то есть мы столкнулись с проблемой существования решения, чтобы либо найти решение, либо обойти все возможности и обнаружить, что решения не существует. После определения алгоритма поиска все остальное просто, у нас есть только два варианта, сначала в глубину или в ширину.
В теории,Чтобы определить существование решения в общем случае, мы используем поиск в ширину для более, потому что в целом он быстрее находит решение. Однако в этом вопросе есть небольшая проблема.Поиск в ширину должен хранить промежуточное состояние в очереди и должен записывать информацию о карте.Каждый раз, когда есть состояние, необходимо хранить информацию о карте .Принесет относительно большие накладные расходы памяти, та же самая хранимая процедура также будет приносить дополнительные вычислительные затраты, что неприемлемо в данной задаче. Потребление пространства, вызванное копированием состояния, по-прежнему невелико, главное — затраты времени на копирование, которых достаточно, чтобы решить эту проблему по таймауту. Так что у нас нет другого выбора, кроме как идти в глубину.
После выяснения алгоритма остается последний вопрос: как найти в этой задаче о прохождении лабиринта вход в лабиринт? Поскольку позиция нашей начальной точки не указана в вопросе, решить ее несложно.Мы проходим через двумерный массив символов, и позиция, совпадающая с началом строки, может использоваться как вход в лабиринт.
Наконец, давайте посмотрим на код, здесь нет технического содержания, просто метод поиска с возвратом.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
fx = [[0, 1], [0, -1], [1, 0], [-1, 0]]
def dfs(x, y, l):
if l == len(word):
return True
for i in range(4):
nx = x + fx[i][0]
ny = y + fx[i][1]
# 出界或者是走过的时候，跳过
if nx < 0 or nx == n or ny < 0 or ny == m or visited[nx][ny]:
continue
if board[nx][ny] == word[l]:
visited[nx][ny] = 1
if dfs(nx, ny, l+1):
return True
visited[nx][ny] = 0
return False
n = len(board)
if n == 0:
return False
m = len(board[0])
if m == 0:
return False
visited = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
for j in range(m):
# 找到合法的起点
if board[i][j] == word[0]:
visited = [[0 for _ in range(m)] for _ in range(n)]
visited[i][j] = 1
if dfs(i, j, 1):
return True
return False
Суммировать
Если вы можете разобраться с методом возврата и достаточно знакомы с реализацией метода возврата, то сложность этого вопроса невелика. На самом деле, до сих пор мы чистили весь путь, и мы сделали несколько задач с возвратом.Я думаю, для вас проблема с возвратом должна быть проще простого.
По сравнению с методом возврата, я думаю, более важно, чтобы мы могли ясно мыслить посредством анализа,Почему не работает поиск в ширину?, Что является существенной причиной для основного ядра. Этот мыслительный процесс часто важнее, чем окончательный вывод.
Если вам понравилась эта статья, пожалуйстаобращать внимание, подбодрите меня и облегчите доступ к другим статьям.
В этой статье используетсяmdniceнабор текста