Найти максимальное количество слов (из данного словаря), которые в совокупности представляют данный текст

Question

Ввод: текст T и набор из n слов в конечном алфавите.

Нам нужно найти самое длинное представление слов, которые при объединении составляют T. Это можно сделать путем объединения слов вместе.

• Не может быть такого представления
• Мы можем использовать одно и то же слово из словаря более одного раза
• Решение должно быть оптимальным
• Нет ограничений на длину вывода

Например, учитывая вывод:

words = {"na", "ba", "banana", "bana" , "a", "nan"}

T = "банан"

Вывод должен быть "ba" "nan" "a", потому что количество слов равно 3. "bana" «na» и «банан» состоят из 2 и 1 слова / с соответственно, поэтому это не максимальное количество слов, и результат должен быть «ba» «nan» «a».

У меня есть пытался решить это с жадным алгоритмом, но он не работает. Итак, я думаю, что решение - это динамическое программирование c, но я не знаю как. Я попробовал другой подход, чтобы сделать это с Tr ie - путем поиска текущей буквы в вершинах tr ie.

• Поиск первой буквы T в Tr ie
• Проверьте другие буквы в вершине, если T не единственная буква в вершине
• Если T является единственной буквой в вершине, проверьте ее дочерние элементы
• Если дети не совпадают с i-й буквой T, снова найдите i-ую букву в Tr ie
• Если буквы на текущей вершине не совпадают, то такого нет репрезентация.

Это оптимальное или даже правильное решение? Если нет, то каково решение для динамического программирования c?

Заранее спасибо!

Answer 1

Вы можете решить эту проблему с помощью динамического программирования c. Вот решение в python с использованием нисходящего подхода с запоминанием

memo = {} # memoization
def find_max(words, t, pos):
    if pos in memo:
        return memo[pos]
    ret = 0
    for i in range(pos+1, 1+len(t)):
        sub = t[pos:i]
        if sub in words:
            ret = max(ret, 1 + find_max(words, t, i))
    memo[pos] = ret
    return ret

words = ["na", "ba", "banana", "bana", "a", "nan"]
t = "banana"
ret = find_max(words, t, 0)   # returns 3

. Вы можете оптимизировать for l oop для более эффективного поиска подходящих слов, начинающихся с pos , Для этого можно использовать Tr ie.