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

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

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

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

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

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

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

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

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

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