java - 如何创建随机字母的单词？

Question

这是我的作业说明:

“构建一个程序，让用户根据随机字母结果创建不同的单词。 这些词必须查字典。”

这是目前的代码:

import java.util.Arrays;



public class AngloTrainer {
// ...

public AngloTrainer(String dictionaryFile) throws IOException {
    // load dictionary?
    //what else?
}

private String sort(String s){

    //Sort the letters in a string. 
    char[] tecken = s.toCharArray();
    String sorted = Arrays.sort(tecken);
    return sorted;

}

// use this to verify loadDictionary
private void dumpDict() {
    // Print out the dictionary at the screen.
      // ... define!
}

private void loadDictionary( String fileName ) {
    // Read the dictionary into a suitable container.
    // The file is a simple text file. One word per line.
    FileReader flr = new Filereader(fileName);  
    BufferedReader bfr = new BufferedReader(flr);
    String line;
    //collection/treeset?? maybe other??
    while((line = bfr.readLine()) !=null ){
        //save to a collention, but which?
    }
}

private String randomLetters( int length ) {
    // this makes vovels a little more likely
    String letters = "aabcdeefghiijklmnoopqrstuuvwxyyz";  
    StringBuffer buf = new StringBuffer(length);
    for ( int i = 0; i < length; i++ ) 
        buf.append( letters.charAt(randomGenerator.nextInt(letters.length())));

    return buf.toString();
}


/* Def. includes    
 * Let #(x,s) = the number of occurrences of the charcter x in the string s.
 * includes(a,b) holds iff for every character x in b, #(x,b) <= #(x,a)
 * 
 * A neccessary precondition for includes is that both strings are sorted
 * in ascending order.
 */
private boolean includes( String a, String b ) {
    if ( b == null || b.length() == 0 )
        return true;
    else if ( a == null || a.length() == 0 )
        return false;

    //precondition: a.length() > 0 && b.length() > 0
    int i = 0, j = 0;
    while ( j < b.length() ) {
        if (i >= a.length() || b.charAt(j) < a.charAt(i))
            return false;
        else if (b.charAt(j) == a.charAt(i)) {
            i++; j++;
        } else if (b.charAt(j) > a.charAt(i))
            i++;
    }
    //postcondition: j == b.length()
    return true;
}




public static void main(String[] args) {
    // ... define!
}
}

我应该为 loadDictionary 方法使用哪个集合？ 如作业所述，我需要根据字典集合检查我输入的单词。

Answer 1

A HashSet提供更好的平均案例理论复杂性 - 但是，请注意 HashSet 根据定义是无序的。这意味着“相关”词之间没有相关性(例如，cat 和 catfish 可以彼此相距很远)。
Hashset 提供 O(1)(或准确地说是 O(|S|)，因为您确实需要读取字符串) 查找和插入。

A TreeSet理论上比 HashSet 慢，并且具有 O(logN)(或者再次，O(|S|logn)，因为字符串仍然需要被阅读)。
但是，TreeSet 是SortedSet 的一个实例.这意味着根据使用的比较器，彼此“接近”的单词也将在其中彼此靠近放置。在 String.compareTo() 的默认实现中- 使用的顺序是 lexicographic order .这意味着共享相同前缀的单词将彼此“接近”。因此，如果您稍后打算扩展您的实现以允许单词完成，例如 - TreeSet 是更好的选择，因为您可以使用 tailSet()它的方法。
TreeSet 也不会受到 O(n) 的最坏情况复杂性的影响，所以如果 latency是您系统中的一个问题 - 它们应该优先于 HashSet，后者偶尔需要 O(n) 操作来维护数据结构。

此外，您可以使用 ArrayList - 并确保使用 Collections.sort() 对其进行排序.它应该可以解决问题，因为您的字典是静态的，而 Set 更侧重于动态(不断变化的字典)。您稍后可以使用 Collections.binarySearch() 查找列表中是否有单词

其他针对字符串优化的数据结构是Trie , Radix tree (一个更节省空间的 trie 变体)。但是 - 这些都没有在内置的 java Collections 库中实现。如果您稍后发现性能问题，并且需要加快代码的这个特定部分的速度 - 您应该考虑切换到非内置数据结构，但作为初学者 - 让事情正常进行，不要过早优化