Возможно ли составить слово из "слогов"?

[Cuprum2020]

Добрый вечер. Решаю задачу тут
Вернуть True если слово возможно составить из слов списка-словаря, False - если нет. Одно и то же слово из словаря может быть использовано много раз, а ещё такое слово может быть подстрокой другого слова

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

Вот код:

Используется синтаксис Python

def new_seq(seq):
    new = seq[:]
    for el in seq:
        for i in range(len(new)):
            while new[i] != el and new[i].startswith(el):
                new[i] = new[i].replace(el, '', 1)
    while '' in new:
        new.remove('')
    if new != seq:
        return new_seq(new)
    return new


def new_word(word, seq):
    new = word
    for w in seq:
        while new.startswith(w):
            new = new.replace(w, '', 1)
    if new != word:
        return new_word(new, seq)
    return new


def valid_word(seq, word):
    seq = list(set(seq))
    seq = new_seq(seq)
    print(seq)
    word = new_word(word, seq)
    return not word


seq = ['cy', 'fczdqcy', 'hzjkfczd', 'hfc', 'h', 'hh', 'fczdqfczd', 'cyh', 'cyhzjk', 'mfcz', 'fczdq', 'cyfcz',
       'fczdqcy', 'cycy']
word = 'cyhhhfczdqcyhzjkfczdqfczdqcycyfczdqcymfczdq'
print(valid_word(seq, word))  # False
 

Проблема кажется мне неустранимой. Поэтому я ищу другие подходы. Например думаю над таким: программа должна искать способ построить слово из имеющихся слогов, но если она заходит в тупик, то возвращаться обратно. Для этой цели я даже придумал оригинальный тест (первая версия программы его кстати успешно проходит):

Используется синтаксис Python

seq = ['abcd', 'abcdd', 'abcdddd', 'ddddefg', 'defg', 'ddfgh', 'ddfghh', 'ddfghhhh', 'hhhhijk', 'hhijk', 'hijk']
word = 'abcddddefghhhhijk'
print(valid_word(seq, word))  # True
 

Тут слово возможно составить только из трёх слогов: 'abcdd', 'ddfghh', 'hhijk'
Третий уже очевиден если найдены первые два. А вот с первыми двумя всё не так просто. Простая "правильная" сортировка списка слов тут не поможет, так как оба раза выбирать надо не самый короткий или самый длинный слог, а средний по длине. И возможны такие ситуации, когда в одном случае (одна первая буква слога) надо выбрать самый длинный слог (или длиннее среднего), а в другом (другая первая буква) - самый короткий (или короче среднего). Я пытался в словаре сохранять эдакое "дерево вариантов" ключ - слог, от которого избавлялось слово, значение - новое слово, когда все такие ключи закончились: ключ - двухэлементный кортеж, второй элемент - второй слог от которого избавлялось слово ранее избавленное от первого, потом уже ключи из трёхэлементных кортежей - но путь показался мне тупиковым с вычислительной точки зрения, в худшем случае факториал (от количества разных слогов) возможных вариантов получается. Или даже хуже, нельзя за раз удалить все вхождения слога в строку, так как в одном месте может потребоваться удалить именно этот слог, а в другом слог частично с первым пересекающийся

UPD Хотя словарь с деревом вариантов и иначе можно строить. Например в приведённом примере слово можно начать раздевать лстрипить с трёх разных слогов, получится три разных ключа-значения, а потом обнаружить что только одно из этих значений можно ещё тремя разными способами лстрипнуть и только один вариант правильный. Но если например слово начинается с английского алфавита, а слоги: a, ab, abc, abcd, ... и так 26 слогов с последним длиной в английский алфавит, а потом ещё какие то?

[ozheredov]

Cuprum2020
Первое что пришло в голову:

1. Берем все слова словаря vocab, и с помощью contains(string, vocab(k)) смотрим, содержит ли строка string данное слово.
2. Таким образом, мы получили состав строки c точностью до перестановок слов.
3. В цикле удаляем эти слова-участки из строкИ.
4. Если что-то осталось - то false, иначе true

-- 11.01.2022, 22:17 --

ПыСы: алгоритм легко модифицируется, если слова входят в строку с пересечениями, т.е. true дает

vocab = {'abc'; 'bcd'} string = {'abcd'}

[Cuprum2020]

ozheredov в сообщении #1545910 писал(а):

ПыСы: алгоритм легко модифицируется, если слова входят в строку с пересечениями, т.е. true дает

vocab = {'abc'; 'bcd'} string = {'abcd'}

Так в этом случае как раз таки нужен False, так как из данных слогов составить строку abcd нельзя. Для теста 'abc' и ['ab', 'bc'] правильным ответом является False, а вот для 'abc' и ['ab', 'a', 'bc'] - True

Цитата:

2. Таким образом, мы получили состав строки c точностью до перестановок слов.
3. В цикле удаляем эти слова-участки из строкИ.
4. Если что-то осталось - то false, иначе true

Так просто не работает. Простейший тест: 'abc' и ['ab', 'a', 'bc'] Удаляем из 'abc' 'ab' и получаем строку 'c' с которой уже сделать ничего нельзя и неверный ответ. Тут надо 'a' сначала удалить, самое "короткое вхождение". А в тесте 'zorgz' и ['z', 'zorg'] удалим самое короткое 'z' и получим 'orgz', тут надо самое длинное вхождение первым удалять. Нет универсального рецепта

[mihaild]

Какие ограничения?
Очевидный вариант - бежим по строке и для каждого префикса смотрим, можно ли получить его конкатенацией слов из словаря. Если аккуратно всё сделать - можно уложиться в $O(n^2 + m)$, где $n$ - длина строки, $m$ - суммарная длина строк в словаре.

[Cuprum2020]

mihaild в сообщении #1545912 писал(а):

бежим по строке и для каждого префикса смотрим, можно ли получить его конкатенацией слов из словаря

Так это вот как сделать то?
Вот на примере 'abc' и ['ab', 'a', 'bc'] и на примере 'zorgz' и ['z', 'zorg'] ?
'a' - можно, тк совпадает с одним из слогов
'ab' - можно, тк совпадает с одним из слогов
'abc' - а вот тут как убедиться что можно?
'z' - можно
'zorg' - можно
'zorgz' - а вот тут как убедиться что можно?

[mihaild]

Cuprum2020 в сообщении #1545913 писал(а):

Так это вот как сделать то?

Префикс длины $n$ можно получить конкатенацией слов из словаря, если он оканчивается словом длины $m$ из словаря и префикс длины $n - m$ тоже можно получить конкатенацией.

[zykov]

Поиском. Либо в глубину, либо в ширину.
Рекурсивная функция (поиск в глубину) в пару строчек пишется.

[Cuprum2020]

mihaild
Как то так

Используется синтаксис Python

def valid_word(seq, word):
    d = {0: True}
    for i in range(len(word)):
        i += 1
        for el in seq:
            if word[:i].endswith(el) and d[i - len(el)]:
                d[i] = True
                break
        else:
            d[i] = False
    return d[len(word)]
 

[ozheredov]

Cuprum2020 в сообщении #1545911 писал(а):

Простейший тест: 'abc' и ['ab', 'a', 'bc']

А, там с повторениями. Тогда сорри.

[mihaild]

Cuprum2020 в сообщении #1545920 писал(а):

Как то так

Ну да. Работает в худшем случае за произведение суммарной длины словаря на длину слова. Но в целом сложность по длине входа лучше квадрата я тут получать не умею.

[wrest]

Cuprum2020 в сообщении #1545906 писал(а):

Для этой цели я даже придумал оригинальный тест (первая версия программы его кстати успешно проходит):

В принципе, вот такой регекс сматчит всю строку abcddddefghhhhijk:
(abcd|abcdd|abcdddd|dddefg|defg|ddfgh|ddfghhh|ddfghhh|hhhhijk|hhijk|hijk|fghh)+
И подобным образом сформированные регексы проходят все тестовые примеры на странице по вашей ссылке.
Но есть нюансы :) Пример со строкой cyhhhfczdqcyhzjkfczdqfczdqcycyfczdqcymfczdq не проходит, из-за "жадности" регулярок.

[mihaild]

wrest в сообщении #1545939 писал(а):

Пример со строкой cyhhhfczdqcyhzjkfczdqfczdqcycyfczdqcymfczdq не проходит, из-за "жадности" регулярок

Вообще-то это баг в движке регулярок, если жадность приводит к пропуску совпадения. Правда работать они могут экспоненциально долго - проверьте ваш метод на словаре a, aa и строке $a^{50} b$ :)

[wrest]

mihaild в сообщении #1545940 писал(а):

Вообще-то это баг в движке регулярок, если жадность приводит к пропуску совпадения.

Она и не приводит. "Жадность" означает что регулярка (abc|abcd)+ сматчит в строке abcd вхождение первой альтернативы, т.е. сматчится abc и остановится (соответственно, получится что всё слово abcd составить нельзя), т.е. порядок следования альтернатив может быть важен. Как их нужно (и можно ли) правильно расположить чтобы работало как надо - это и есть "нюансы".

[mihaild]

wrest в сообщении #1545941 писал(а):

Она и не приводит.

Тогда что значит "пример не проходит из-за жадности"?

wrest в сообщении #1545941 писал(а):

Как их нужно (и можно ли) правильно расположить чтобы работало как надо - это и есть "нюансы".

Если движок без багов - то регулярку вида ^(w1|w2|w3|...)$ он должен сматчить одинаково независимо от порядка слов.

[wrest]

mihaild в сообщении #1545943 писал(а):

Тогда что значит "пример не проходит из-за жадности"?

Не матчится вся строка.

-- 12.01.2022, 16:13 --

mihaild в сообщении #1545943 писал(а):

Если движок без багов - то регулярку вида ^(w1|w2|w3|...)$ он должен сматчить одинаково независимо от порядка слов.

Только сам факт срабатывания, но не то, что именно (какая из альтернатив) сматчилась. Подробнее тут: https://www.regular-expressions.info/alternation.html после заголовка "Remember That The Regex Engine Is Eager"