дано слово, образующее осмысленное слово путем добавления пробелов между ними
Вам дан пример строки «Iamastudent» без пробелов. Вам будет предоставлена предопределенная функция словаря, которая проверяет, присутствует ли данное слово в словаре или нет. Используя эту функцию, вы должны вставить пробелы в строку и напечатать ее как «Я студент».
это мой вопрос на собеседовании и сказал мне тоже решить в C ++, я решил с помощью динамического программирования, но он не был удовлетворен
решение, которое я дал,
так же, как в приведенном ниже вопросе
Данную фразу без пробелов добавить пробелы, чтобы сделать правильное предложение
он попросил меня сделать это с помощью Trie или же массив суффиксов но я не могу понять, может ли решение помочь мне
Решение
Найдите слова и поставьте после них пробелы
Ответ заключается в использовании структуры данных Trie. Создайте Trie с возможными словами и продолжайте обход. с Trie вы можете генерировать много разных возможных слов.
теперь здесь «iamastudent» с Trie вы можете генерировать эти слова.
i, a, am, a, as, student
теперь вы должны составить правильное предложение из этих слов. Здесь возможное решение — цепь Маркова. Цепочка Маркова — это структура данных, в которой хранится вероятность следующего слова после слова. так что цепочка марков будет.
"i" : [ "am", "did", "went" ...],
"a" : [ "tree", "dog" ..]
"am" : [ "a" ...]
Теперь вы эти много данных в последовательности
[i], [a, am], [a, as], [student]
Примечание: я сгруппировал все элементы, начинающиеся с одного символа, в один
список.
начать с «я»
Следующее слово «а». но в марковской цепочке «а» нет. так что перейдите к следующему слову. как это вы можете продолжить.
с этого момента это поиск в dfs правильного предложения. ну, это был хороший и сложный вопрос.
Другие решения
Если существует уникальное решение для разбиения предложения, то сделать это с помощью tree очень просто:
- если во входной строке есть символы, начинайте спуск с корня, потребляющего символы из строки. в противном случае прекратить.
- если это сжатый три, вы найдете отметку, когда префикс является полным словом, в противном случае, если вы достигнете листа, это когда вы выводите пробел
- вернуться к 1 (спускаясь от корня), начиная с текущей позиции в строке
Вы закончили, когда в строке больше нет символов (вы можете проверить, что в этот момент вы не пересекаете дерево).
Если решение не уникально, тогда, когда вы достигнете конца строки и у вас нет метки или листа в дереве, вам необходимо вернуться к предыдущему пробелу, который вы испустили. Вам нужен стек для позиций во входной строке.