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 個のバリエーションがあると思いますか?)

私の質問はこれです：

母音の多い単語の場合に、より迅速に結果が得られるように、この問題にどのようにアプローチできますか?

編集: n^6 ではなく、6^n のバリエーション

4

1 に答える 1

-1

6^n の値は、問題の複雑さを示します (また、元の単語の各文字を反復処理して母音か子音かを確認するのに必要な時間がありますが、比較すると小さすぎるはずです)。 . それを変更する正気の方法はありません。実際に行っているのは、0 から (6^n) - 1 までを基数 6 で数えることです。

とにかく、コードはそれを行っていません。毎回母音の1つを置き換えるだけで、すべての可能性を探るわけではなく、値をn * 6のままにします。最後の母音をそのままにしておくと、「ルート」から取得されます

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

私の見解は

1) 空の文字列 "" を結果のリストに追加します

2) 文字が子音の場合、リスト内のすべての文字列の後ろに追加します。以前の値を削除します (文字列は不変であるため、リスト内のオブジェクトを変更するだけではなく、削除して新しいバリエーションを追加する必要があります)。

3) 文字が母音の場合、リスト内のすべての文字列を取得し、各母音を順番に配置します。これらの結果をすべてリストに追加します (以前の結果は削除します)。[以前の文字列数] の 6 倍になります。

4) 繰り返す

于 2013-05-17T00:55:42.777 に答える