Первый поиск глубины или рекурсия возврата для нахождения всех возможных комбинаций букв на доске кроссвордов?

Question

Какова будет сложность времени? Я просто хочу избежать этого, будучи O (n!). Будет ли использование поиска вначале глубины сложностью по времени O (n ^ 2), поскольку для каждой буквы может потребоваться пройти все остальные буквы в худшем случае?

Думаю, я не уверен, правильно ли я думаю об этом.

Когда я говорю "сначала использовать поиск по глубине", я имею в виду, что сначала поиск по глубине начинается с первой буквы, а затем начинается со второй буквы и т. Д.

Это необходимо?

Замечания:
Первоначальная проблема - найти все возможные слова на доске кроссвордов. Я думаю об использовании структуры данных trie, чтобы найти, есть ли слово в словаре, но я думаю о способах генерации самих слов.

Answer 1

После обсуждения выше, вот мой ответ:

Определение: trieX это поддерево, со словами длины X только.

Поскольку у нас есть список всех слов на желаемом языке, мы также можем получить соответствующий trieX,

Мы говорим, что кроссворд w слова, поэтому мы создаем массив w долго, где каждая запись является корнем TrieX, где X длина соответствующего слова. Это дает нам список возможных слов в каждом пустом слове.

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

Два замечания:
1. Для повышения производительности мы начинаем с добавления либо длинных слов, либо ОЧЕНЬ коротких. Что короткое или длинное? посмотрите на это и это.
2. Исключение слов из trieX также можно сделать, проверив зависимости между словами (если ЭТО слова находятся здесь, то ЭТОГО слова не может быть там и т. Д.). Это более сложно, поэтому, если кто-то хочет добавить некоторые идеи о том, как это легко сделать - пожалуйста, сделайте это.