1

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

例如，如果单词是“root”，则生成的 Set 看起来类似于：

{"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

4

1 回答 1

-1

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

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

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

我的看法是

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

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

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

4) 重复

于 2013-05-17T00:55:42.777 回答