java — поиск в глубине или рекурсия возврата для нахождения всех возможных комбинаций букв на доске кроссвордов?
Какова будет сложность времени? Я просто хочу избежать этого существа На!). Будет ли использование первого поиска глубины быть сложным по времени O (N ^ 2), что касается каждой буквы, возможно, придется пройти все остальные буквы в худшем случае?
Думаю, я не уверен, правильно ли я думаю об этом.
Когда я говорю «сначала использовать поиск по глубине», я имею в виду, что сначала поиск по глубине начинается с первой буквы, а затем начинается со второй буквы и т. Д.
Это необходимо?
Замечания:
Первоначальная проблема — найти все возможные слова на доске кроссвордов. Я думаю об использовании структуры данных Trie, чтобы найти, есть ли слово в словаре, но я думаю о способах генерации самих слов.
Решение
После обсуждения выше, вот мой ответ:
Определение: trieX это поддерево, со словами длины X только.
Поскольку у нас есть список всех слов на желаемом языке, мы также можем получить соответствующий trieX,
Мы говорим, что кроссворд w слова, поэтому мы создаем массив w долго, где каждая запись является корнем TrieX, где X длина релевантного слова. Это дает нам список возможных слов в каждом пустом слове.
Затем переберите пересечения между словами и исключите слова, которые нельзя поместить. Когда больше нет изменений — мы останавливаемся.
Два замечания:
1. Чтобы повысить производительность, мы начинаем с добавления либо длинных слов, либо ОЧЕНЬ коротких. Что короткое или длинное? посмотри на этот а также этот.
2. Исключение слов из trieX также можно сделать, проверив зависимости между словами (если ЭТО слова находятся здесь, то ЭТОГО слова не может быть там и т. Д.). Это более сложно, поэтому, если кто-то хочет добавить некоторые идеи о том, как это легко сделать — пожалуйста, сделайте это.
Другие решения