#нужно найти все слова из списка words, которые есть в матрице board class Solution3: def find_index(self, search_matrix, symbol): """ Функция поиска всех положений symbol в матрице search_matrix. Возвращает список кортежей с позициями symbol в виде [(i1, j1), ... (in, jn)] """ result_list = [] for i, v in enumerate(search_matrix): for j, v2 in enumerate(v): if v2 == symbol: result_list.append((i, j)) return result_list def next_index(self, positions_list, max_str_index, max_clmn_index): """ Функция поиска соседей текущей позиции positions_list[-1]. Position_list содержит последовательные координаты (i, j) букв искомого слова в матрице Соседи не должны выходить за границы матрицы max_str_index и max_clmn_index и не должны уже находиться в position_list Возвращает список кортежей с позициями соседей в виде [(i1, j1), ... ] """ i, j = positions_list[-1] all_neighbours = [(i-1, j), (i, j+1), (i+1, j), (i, j-1)] return [x for x in all_neighbours if 0<=x[0]<=max_str_index and 0<=x[1]<=max_clmn_index and x not in positions_list] def find_word(self, board, word, start_position, max_str_index, max_clmn_index): """ Функция поиска слова word в матрице board Возвращает функцию check_matrix() """ #создаём список в который будем добавлять координаты (i,j) последующей найденной буквы искомого слова lettersIndexesList = [start_position,] #устанавливаем флаг нахождения слова в матрице isWordInBoard = False #индекс следующей проверяемой буквы слова word nextLetterIndex=1 def check_matrix(board, word, max_str_index, max_clmn_index): #даём доступ функции к переменным find_word, поскольку их состояние должно сохраняться nonlocal isWordInBoard nonlocal nextLetterIndex #находим соседей для последнего добавленного элемента в lettersIndexesList all_neighbours = self.next_index(lettersIndexesList, max_str_index, max_clmn_index) #устанавливаем счётчик проходения соседей num_neighbours = len(all_neighbours) #если соседей нет или всех соседей обошли и ничего больше не добавили в lettersIndexesList, #то удаляем последний элемент из lettersIndexesList, потому что он тупиковый и понижаем nextLetterIndex if num_neighbours == 0: del lettersIndexesList[-1] nextLetterIndex -= 1 print('###############################') print('del lettersIndexesList') print(lettersIndexesList) print('###############################') #если в lettersIndexesList было несколько элементов и удалили только последний, #то пытаемся продолжать итерировать по соседям предыдущего элемента if not lettersIndexesList: check_matrix(board, word, max_str_index, max_clmn_index) #если в lettersIndexesList был только один элемент и он оказался удалён, #то возвращаем False, поскольку позиция первый буквы слова сразу оказалась тупиковой else: return isWordInBoard ###Вот где-то здесь и находится косяк, во-первых, удаление элемента осуществяется вне цикла, ###так что после удаления непонятно как возратиться к итерированию по соседям предыдущего элемента ###Во-вторых, бывает такая ошибка, что в lettersIndexesList удаляется -1 элемент, но у -2 не осталось соседей, ###поэтому они ищутся у -3, при этом -2 остаётся в списке, в результате у нас может получиться последовательность координат ###которые находятся не рядом друг с другом #если соседи у последнего элемента списка lettersIndexesList есть else: for neighbour_position in all_neighbours: print('^^^^^^^^^^^^^^^^^^^^^^^^^^^') print('main loop all_neighbours') print(all_neighbours) print('len all_neighbours') print(len(all_neighbours)) print('num_neighbours') print(num_neighbours) #print('***********************************') print('lettersIndexesList') print(lettersIndexesList) #print('***********************************') print('^^^^^^^^^^^^^^^^^^^^^^^^^^^') #уменьшаем счётчик оставшихся для проверки соседей num_neighbours-=1 #распаковываем текущий кортеж на отдельные элементы i, j = neighbour_position print('neighbour_position') print(neighbour_position) print('nextLetterIndex') print(nextLetterIndex) #сравниваем букву с координатами i,j с буквой слова word по индексу nextLetterIndex if board[i][j] == word[nextLetterIndex]: print('[i][j]') print((i, j)) #если они равны, то добавляем координаты совпавшей буквы в lettersIndexesList lettersIndexesList.append(neighbour_position) #если достигли конца слова, то заканчиваем цикл и возвращаем True - слово word есть в матрице board if nextLetterIndex == len(word)-1: print('lettersIndexesList') print(lettersIndexesList) print('word') print(word) isWordInBoard = True break #в противном случае продолжаем поиск рекурсивно else: nextLetterIndex += 1 check_matrix(board, word, max_str_index, max_clmn_index) #если не совпало, переходим к следующему элементу else: continue return isWordInBoard return check_matrix(board, word, max_str_index, max_clmn_index) def findWords(self, board, words): """ Функция для нахождения всех слов, входящих в матрицу board Возвращает список строк """ #список для слов, входящих в матрицу board result_words = [] #размерности матрицы board M = len(board) N = len(board[0]) #общее количество элементов в матрице total_elements = M*N #итерируем по списку слов for word in words: #если количество букв в слове больше количества букв в матрице, то пропускаем слово и итерируем дальше if total_elements < len(word): continue else: #находим все вхождения первой буквы слова в виде списка кортежей с координатами start_positions = self.find_index(board, word[0]) #итерируем по этому списку кортежей for start in start_positions: print('start_positions') print(start_positions) print('start') print(start) print('word') print(word) #если слово ещё не добавлено в result_words, если длина слова равно 1 #или если find.words() возвращает True, добавляем слово в конечный список result_words if word not in result_words and \ (len(word)==1 or self.find_word(board, word, start, M-1, N-1)): result_words.append(word) break else: continue return result_words board3 = [["d","c","e","b","d","e","d","a"], ["c","a","e","a","d","d","e","e"], ["a","c","e","d","b","c","c","b"], ["c","b","a","a","a","e","e","e"], ["a","e","d","e","b","d","d","e"], ["a","a","d","c","e","a","d","e"], ["b","d","e","b","b","b","c","e"], ["d","a","e","e","b","e","b","d"], ["b","b","c","a","b","b","b","a"], ["a","c","b","a","c","a","d","d"]] words3 = ["ab","bddbebcba","ededa","daebeda","edecaeabc","cbeedad","bcaaecb","c","eb","aadbdbacee","dcaaba"] #Expected output: ["c","eb","ededa","ab","daebeda"] Solution3().findWords(board3, words3)