Как можно найти слова, которые даны во втором массиве в первом массиве

Question

Например, у меня есть два txt-файла, один из них содержит текст

vlrtakeon
itredflow
ntuemturn
trgteaylp
arraysryi
gshjshhkg
etoesingg

а второй содержит

vintage
take
flow
remark
tea
array
toe
sing
turn
red
pig

Выступом будет массив, который содежит те элементы, которые не использовались для поиска слов.

Я открыл каждый файл и добавил их в два массива

with open("puzzle.txt") as f:
    puzzle = [list(line.strip()) for line in f]
with open("words.txt") as f:
    words = [list(line.strip()) for line in f]

Специально добавил текст в массив так, чтобы каждая буква была элементом массива, потому что ищу слова не только горизонтально, но еще вертикально и по диагонали.

Решил написать три функции, которые ищут слова горизонтально, вертикально и по диагонали. И теперь не могу понять, как искать эти слова и считались буквы именно в этом порядке. Знаю только как находить элементы, но слова - это же порядок букв а не один элемент. Изначально думал удалять все слова, которые есть в первом массиве, но некоторые буквы используются по несколько раз.

Можете, пожалуйста, помочь хотя бы с поиском по вертикали, чтобы мог понять, как вы ищете эти слова в первом массиве.

Answer 1

Определим необходимые значения:

elements = ['vlrtakeon',
         'itredflow',
         'ntuemturn',
         'trgteaylp',
         'arraysryi',
         'gshjshhkg',
         'etoesingg']

words = ['vintage'
          'take',
          'flow',
          'remark',
          'tea',
          'array',
          'toe',
          'sing',
          'turn',
          'red',
          'pig']

Пример решения "по горизонтали":

for word in words:
    for element in elements:
        if word in element:
            print(word, ' входит в ', element)

Консоль:

# flow входит в itredflow
# tea входит в trgteaylp
# array входит в arraysryi
# toe входит в etoesingg
# sing входит в etoesingg
# turn входит в ntuemturn
# red входит в itredflow

Пример решения "по вертикали":

verical_words = [] # Создадим массив для слов по вертикали
every_element_len = 9  # Зададим значение для длины каждого слова
for i in range (0, every_element_len): # Пройдемся циклом от 0 до заданной длины каждого слова
    vertical_word = [] # Создадим массив для каждого знака вертикального слова
    for element in elements: # Пройдемся циклом по всем элементам 
        vertical_word.append(element[i]) # Наполним массив для каждого знака значениями

    verical_words.append(''.join(vertical_word)) # Конвертируем знаки в строковые значения

# Выполним поиск (смысл vertical_word заменится):
for word in words: 
    for vertical_word in verical_words:
        if word in vertical_word:
            print(word, ' входит в ', vertical_word)

Консоль:

# vintage  входит в  vintage
# pig  входит в  nwnpigg

Answer 2

list1 = [[]] 
list2 = []
# Поиск по горизонтали
for i in range(len(list1)):
    for word in list2:
        if word in ''.join(list1[i]):
            print(f'Word {word} in {list1[i]}')
vertical_words = []
word = ''
# Составляем массив со словами по вертикали
for i in range(len(list1[0]))
    for j in range(len(list1)):
        word += list1[j][i]
    vertical_words.append(word)
    word = ''
# Поиск по вертикали
for ver_word in vertical_words:
    for word in list2:
        if word in ver_word:
            print(f'Word {word} in {ver_word}')
# Поиск слов по диагонали
gor_words = []
gor_word = ''
for i in range(len(list1[0])):
    x = i
    y = 0
    while x < len(list1[x]) and y < len(list1)
        gor_word += list1[y][x]
        x += 1
        y += 1
    gor_words.append(gor_word)
    gor_word = ''
for i in range(len(list1)):
    x = i
    y = 0
    while y < len(list1[x]) and x < len(list1)
        gor_word += list1[x][y]
        x += 1
        y += 1
    gor_words.append(gor_word)
    gor_word = ''
for goriz_word in gor_words:
    for word in list2:
        if word in goriz_word:
            print(f'Word {word} in {goriz_word}')

Этот алгоритм поиска не очень быстрый Для поиска по горизонтали O(nm), где n(длина list1) m(длина list2) Для поиска по вертикали O(nm+i*k), где n(длина list1[0]) m(длина list1) k(длина list2) i(длина vertical_words)

БЛОГ НА HUSL

Как можно найти слова, которые даны во втором массиве в первом массиве

Ответы (2 шт):