Решатель беспорядочных букв Objective-C

Question

Я пытаюсь создать это приложение на iphone с 6 буквами, оно выведет все возможные английские слова из 3-6 букв. У меня уже есть словарь, я просто хочу знать, как это сделать.

Я искал вокруг и нашел только те решатели скрэббл в Python или эти решения для поиска по словам.

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

Спасибо!

Answer 1

Если вы беспокоитесь о производительности, этот метод может помочь.Он включает некоторую предварительную обработку, но допускает почти мгновенный поиск анаграмм.

1. Создание структуры данных, которая отображает ключ String в список строк (я больше знаком с Java,так что в этом случае это будет Map<String,List<String>>). Здесь будет храниться ваш словарь.

2. Определите функцию, которая принимает строку и выводит те же буквы, расположенные в алфавитном порядке.Например, hello станет ehllo;kitchen станет cehiknt.Я буду ссылаться на эту функцию как keyify(word)

3. Вот часть предварительной обработки: для каждого элемента в вашем словаре найдите список для ключа этого элемента (keyify(item)) и добавьте этоэлемент к списку.

4. Когда придет время искать анаграммы данного слова, просто посмотрите в списке их keyify этого слова.Например, если ввод был kitchen, keyify будет cehiknt, и поиск этого на вашей карте должен привести к списку, содержащему kitchen, chicken и любые другие анаграммы кухни, которые я забыл: P

Answer 2

Я столкнулся с этой проблемой несколько недель назад, и самый эффективный способ выяснить, как ее решить, был

Я нашел все подмножества данной строки (это займет O (2 ^ n))

Затем я заглянул в свой словарь, чтобы увидеть, «не использует ли подмножество» все символы всех строк этого размера

например, заданная строка "hetre" и слова "там она" в твоем словаре Вы можете рассчитать все подмножества

{h} {e} {t} {r} {e} {he} {ht} {hr} {he} {het} {her} {reh} ... есть 32 подмножества "hetre"

, затем проверьте, похожи ли какие-либо из этих подмножеств на слова в словаре в этом случае Рех похож на нее, что означает, что это слово, которое будет использоваться

Это был самый эффективный способ, которым я мог придумать

исследуйте PowerSets и подумайте, как можно написать функцию, которая "использует" строки

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

Мой не доставлял мне проблем, пока я не начал вводить строки длиной более 15 символов, используя первый метод. используя второй метод, у меня не было проблем до 7

Answer 3

Проверьте этот ответ: Алгоритм генерации анаграмм .. Посмотрите на ответ Джейсона Коэна. Сформулируйте по буквам 6-буквенное слово, затем просмотрите ваш словарь и скомпонуйте это слово и сравните.