Java - 查找元音互换的单词的所有可能形式

Question

给定一个包含元音的单词，我正在尝试编写一种方法，该方法将发现通过交换其元音而创建的该单词的所有可能排列。

例如，如果单词是“root”，则结果集将类似于:

{"roat", "roet", "roit", "rout", "royt", "reet", "riot", "reat" ...}

我最初的策略是将其视为递归回溯问题，我编写了以下方法:

public static final String VOWELS = "aeiouy";

    ...

    vowelSwap(emptySet, listRepresentingString, 0); // the initial recursive call

private void vowelSwap(Set<String> swaps, List<Character> list, int start) {
        for (int i = start; i < list.size(); i++) {
        if (isVowel(list.get(i))) {
            // do some vowel swapping on this character
            for (int j = 0; j < VOWELS.length(); j++) {
                if (list.get(i) != VOWELS.charAt(j)) {
                    char temp = list.get(i);
                    list.set(i, VOWELS.charAt(j));
                    String s = stringify(list);
                    swaps.add(s);
                    vowelSwap(swaps, list, i + 1);
                    list.set(i, temp);
                }
            }
        }
}

public static String stringify(List<Character> list) {
    ...
    a method that converts a List<Character> to String
}

它可以工作，但是当单词中有大量元音时，运行时间会很糟糕。 (给定一个单词中的 n 个元音，我相信有 6^n 个变体？)

我的问题是这样的:

对于含有许多元音的单词，我怎样才能以更快的速度解决这个问题？

编辑:6^n 个变体，而不是 n^6

Answer 1

6^n 值给出了问题的复杂性(此外，需要时间遍历原始单词中的每个字母来检查它是元音还是辅音，但这应该太小了相比)。没有明智的方法可以改变这一点，您所做的实际上是从 0 数到 (6^n) - 1，以 6 为基数。

无论如何，您的代码并没有这样做，它只是每次替换其中一个元音，并且不会探索所有可能性，将值保留为 n*6。当您将最后一个元音保留在适当的位置时，您将从“root”得到

raot, reot, riot, root, ruot, ryot, ryat, ryet ....

我的看法是

1) 将空字符串“”添加到结果列表中

2) 如果字母是辅音，则将其添加到列表中所有字符串的后面。删除以前的值(字符串是不变的，因此您不能只修改列表中的对象，您必须删除它并添加新的变体)。

3) 如果字母是元音，则获取列表中的所有字符串，然后依次放入每个元音。将所有这些结果添加到列表中(并删除以前的结果)。您将获得 6x[之前的字符串数量]

4)重复