Java - 查找所有可能的單詞與元音交換

給定一個包含元音的單詞，我試圖編寫一個方法來發現通過交換元音創建的所有可能的單詞排列。Java - 查找所有可能的單詞與元音交換

舉例來說，如果這個詞是「根」的結果集將類似於：

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

來源

2013-05-17 user2392022

運行時不應該是壞的，我的意思是'N = 10'，只有百萬的變化，那是一個眨眼 –

6^n的值給你的問題的複雜性（也有通過在原來的字中的每個字母來進行迭代所需的時間檢查它是否是一個vower或者輔音，但是在比較中它應該太小）。沒有一種理智的方法來改變這種情況，你在做的事實上是從0到（6^n） - 1，以6爲基數。

無論如何，你的代碼沒有這樣做，它只是取代元音每次都沒有探索所有可能性，將值留給n * 6。當你留在原地的最後元音，你會得到，從「根」

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

我採取的是

1）添加空字符串「」到結果

名單2）如果letter是輔音，則將其添加到列表中的所有字符串後面。刪除以前的值（字符串不變，因此您不能只修改列表中的對象，您必須刪除它並添加新的變體）。 3）如果letter是一個元音，則獲取列表中的所有字符串，並依次放置每個元音。將所有這些結果添加到列表（並刪除以前的結果）。您將獲得6倍[串的前一個數字]

4）重複

來源

2013-05-17 00:55:42 SJuan76

固定這個問題呢，@SJuan76能否爲我澄清一下，我沒有探索這種解決方案的所有可能性？我想在每次遞歸調用後，list.set（i，temp）調用正在做「unchoosing」 – user2392022

我沒有注意到你重置了元音值，不管怎樣，你仍然沒有找到所有的組合（你會得到「ra，re，暴動，根，ru，ryot，roat，roet ....」） – SJuan76

Java - 查找所有可能的單詞與元音交換

回答

相關問題