一個字Anagram的大-O

我創建了一個程序，需要一個字符串，如「computer」，並輸出所有可以由其構成的字典單詞。然而，我試圖弄清楚程序的Big-O效率是多少，因爲它使用遞歸和二進制搜索。一個字Anagram的大-O

此外，該程序可以提高效率嗎？我還沒有研究hashmaps或其他數據結構。

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.*; 

public class WordScramble { 

    static String[] dictArr; 
    static int index; 

    // print permutation/combination of the characters of the string s (in order) 
    public static void permWord(String s) { permWord("", s); } 

    private static void permWord(String prefix, String s) { 
     int n = s.length(); 
     if (n != 0){ 
      for (int i = 0; i < n; i++) 
       permWord(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, n)); 
     } 
     index = Arrays.binarySearch(dictArr, prefix); 
     if (index > 0) 
      System.out.println(prefix); 
    } 
    public static ArrayList<String> getLines(File f) throws FileNotFoundException { 
     ArrayList<String> dict = new ArrayList<String>(); 
     Scanner scan = new Scanner(f); 
     while (scan.hasNext()){ 
      dict.add(scan.next()); 
     } 
     scan.close(); 
     return dict; 
    } 
    public static void main(String[] args) throws FileNotFoundException { 
     File f = new File("wordlist.txt"); 
     ArrayList<String> dictionary = getLines(f); 
     dictArr = new String[dictionary.size()]; 
     dictArr = dictionary.toArray(dictArr); 
     permWord("computer");  
    } 
}

來源

2014-01-19 matt

只要想想邏輯而不是實施。一串長度爲「n」的字符串有多少個排列？對於每個人都有一個二進制搜索。答案是'n！' - 所以複雜度是'n！ln（k）'，其中'n'是單詞的長度，'k'是字典的大小。實際上'n！'的任何倍數都很小，所以這裏最大的問題是'n'的大小，而不是字典的大小。 –

@BoristheSpider這可能是一個答案... – Dukeling

這個問題可能會在codereview.stackexchange.com上做得更好，特別是你問的部分是否可以提高效率。 – yshavit

更好的方法是掃描字典並檢查哪些字是原始字的字形。

您可以通過匹配原始單詞中每個字母的計數來進行檢查。

複雜度O（k）其中k是詞典中所有單詞的總字母數。

此鏈接顯示瞭解決此類問題的更多方法。 Best algorithm to find anagram of word from dictonary

來源

2014-01-19 04:43:29

我喜歡這個。當輸入單詞的大小大於9時，我的原始方法失敗，搜索次數爲9！或362880，這是我的單詞列表的兩倍，並且只有更長的單詞纔會呈指數級惡化。 – matt

一個字Anagram的大-O

回答

相關問題