Строки и возможные анаграммы этих строк - PullRequest
Новая
       21

Строки и возможные анаграммы этих строк

0 голосов
/ 08 июня 2011

Я работаю над крошечным проектом (на Java), пока uni отсутствует, просто чтобы проверить себя, и я наткнулся на камень преткновения.

Я пытаюсь написать программу, которая будет читать стекстовая версия словаря, сохраните ее в ds (структура данных), затем попросите пользователя ввести случайную строку (предпочтительно бессмысленную строку, но только буквы и -и, никаких цифр или других знаков препинания - меня это не интересует)что-нибудь еще), найдите все анаграммы введенной строки, сравните ее со словарем ds и верните список всех возможных анаграмм, которые есть в словаре.

Хорошо, для шага 1 и 2 (чтениеиз словаря), когда я читаю все, что хранится на карте, ключи - буква алфавита, а значения - ArrayLists, в которых хранятся все слова, начинающиеся с этой буквы.

I 'Я застрял в поиске всех анаграмм, я понял, как вычислить количество возможных перестановок рекурсивно (гордо), и я не уверен, как на самом деле делать задниеrange.

Лучше ли разбить его на char и поиграть с ним таким образом, или разбить его и сохранить как строковые элементы?Я видел пример кода в Интернете на разных сайтах, но я не хочу видеть код, я хотел бы знать, какой подход / идеи лежат в основе разработки решения для этого, поскольку я как бы застрял, как начать: (

Я имею в виду, я думаю, я знаю, как я собираюсь провести сравнение со словарем ds после того, как я сгенерировал все перестановки.

Любой совет будет полезен, но не код, если этовсе будет в порядке, просто идеи.

PS Если вы хотите увидеть мой код до сих пор (по любой причине), я выложу то, что у меня есть.

Ответы [ 3 ]

4 голосов
/ 08 июня 2011 
public String str = "overflow";
public ArrayList<String> possibilities = new ArrayList<String>();
public void main(String[] args)
{
    permu(new boolean[str.length()],"");
}
public void permu(boolean[] used, String cur)
{
    if (cur.length()==str.length())
    {
        possibilities.add(cur);
        return;
    }
    for (int a = 0; a < str.length(); a++)
    {
        if (!used[a])
        {
            used[a]=true;
            cur+=str.charAt(a);
            permu(used,cur);
            used[a] = false;
            cur = cur.substring(0,cur.length()-1);
        }
    }
}

Простой с действительно ужасным временем выполнения, но он выполнит свою работу.

РЕДАКТИРОВАТЬ: Более продвинутая версия этого слова называется Trie Dictionary.По сути, это дерево, в котором каждый узел имеет 26 узлов, по одному на каждую букву в алфавите.И у каждого узла также есть логическое значение, указывающее, является ли это концом слова.При этом вы можете легко вставить слова в словарь и легко проверить, правильно ли вы указали путь для создания слова.

Я вставлю код, если вы хотите

3 голосов
/ 08 июня 2011

Вычисление перестановок действительно кажется плохой идеей в этом случае.Например, слово «переполнение» имеет 40320 перестановок.

Лучший способ выяснить, является ли одно слово перестановкой другого, состоит в подсчете, сколько раз встречается каждая буква (это будет 26-кортеж) исравните эти кортежи друг с другом.

2 голосов
/ 08 июня 2011

Может быть полезно, если вы привели пример, чтобы прояснить проблему.Насколько я понимаю, вы говорите, что если пользователь введет, скажем, «islent», программа ответит «listen», «silent» и «enlist».

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

Чтобы продолжить приведенный выше пример, когда мы строим диктовку и увидим слово «слушай», мы переведем это на «eilnst»и хранить "eilnst -> listen".Мы также храним "eilnst -> silent" и "eilnst -> enlist".Затем мы получаем строку ввода, конвертируем ее в «eilnst», делаем поиск и сразу находим три попадания.

...