Блог

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

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

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

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

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

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

Любой совет был бы полезен, но не код, если это было бы нормально, просто идеи.

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

 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);
        }
    }
}
  

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

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

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

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

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

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

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

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