9

我写了一个小程序，试图找到两个长度相等的英语单词之间的联系。单词 A 将通过一次更改一个字母来转换为单词 B，每个新创建的单词都必须是一个英文单词。

例如：

Word A = BANG
Word B = DUST

结果：

BANG -> BUNG ->BUNT -> DUNT -> DUST

我的过程：

  1. 将英文单词表（由 109582 个单词组成）加载到 aMap<Integer, List<String>> _wordMap = new HashMap();中，key 将是单词长度。

  2. 用户输入 2 个字。

  3. createGraph 创建一个图。

  4. 计算这两个节点之间的最短路径

  5. 打印出结果。

一切正常，但我对第 3 步所花费的时间不满意。

看：

Completely loaded 109582 words!
CreateMap took: 30 milsecs
CreateGraph took: 17417 milsecs
(HOISE : HORSE)
(HOISE : POISE)
(POISE : PRISE)
(ARISE : PRISE)
(ANISE : ARISE)
(ANILE : ANISE)
(ANILE : ANKLE)
The wholething took: 17866 milsecs

我对在步骤 3中创建图表所花费的时间不满意，这是我的代码（我使用 JgraphT 作为图表）：

private List<String> _wordList = new ArrayList();  // list of all 109582 English words
private Map<Integer, List<String>> _wordMap = new HashMap();  // Map grouping all the words by their length()
private UndirectedGraph<String, DefaultEdge> _wordGraph =
        new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);  // Graph used to calculate the shortest path from one node to the other.


private void createGraph(int wordLength){

    long before = System.currentTimeMillis();
    List<String> words = _wordMap.get(wordLength);
    for(String word:words){
        _wordGraph.addVertex(word);  // adds a node
        for(String wordToTest : _wordList){
            if (isSimilar(word, wordToTest)) {        
                _wordGraph.addVertex(wordToTest);  // adds another node
                _wordGraph.addEdge(word, wordToTest);  // connecting 2 nodes if they are one letter off from eachother
            }
        }            
    }        

    System.out.println("CreateGraph took: " + (System.currentTimeMillis() - before)+ " milsecs");
}


private boolean isSimilar(String wordA, String wordB) {
    if(wordA.length() != wordB.length()){
        return false;
    }        

    int matchingLetters = 0;
    if (wordA.equalsIgnoreCase(wordB)) {
        return false;
    }
    for (int i = 0; i < wordA.length(); i++) {

        if (wordA.charAt(i) == wordB.charAt(i)) {
            matchingLetters++;
        }
    }
    if (matchingLetters == wordA.length() - 1) {
        return true;
    }
    return false;
}

我的问题：

如何改进我的算法以加快流程？

对于正在阅读本文的任何 redditors，是的，我在昨天看到 /r/askreddit 的线程后创建了这个。

4

3 回答 3

18

这是一个开始的想法：

创建一个Map<String, List<String>>（或Multimap<String, String>如果您使用番石榴），并且对于每个单词，一次“删除”一个字母，并将原始单词添加到该被删除单词的列表中。所以你最终会得到：

.ORSE => NORSE, HORSE, GORSE (etc)
H.RSE => HORSE
HO.SE => HORSE, HOUSE (etc)

那时，给定一个单词，您可以很容易地找到与之相似的所有单词 - 只需再次执行相同的过程，但无需添加到地图中，只需获取每个“空白”版本的所有值。

于 2012-11-10T18:36:17.790 回答
0

您可能需要通过分析器运行它以查看大部分时间都花在了哪里，特别是因为您正在使用库类 - 否则您可能会付出很多努力但看不到明显的改进。

您可以在开始之前将所有单词小写，以避免equalsIgnoreCase()每次比较时都出现。实际上，这是您的代码中的不一致 - 您equalsIgnoreCase()最初使用，但随后以区分大小写的方式比较字符：if (wordA.charAt(i) == wordB.charAt(i)). 完全消除检查可能是值得的，因为这与以下循环equalsIgnoreCase()基本相同。charAt

您可以更改比较循环，以便在找到多个不同的字母时尽早完成，而不是比较所有字母，然后才检查有多少匹配或不同。

（更新：这个答案是关于优化您当前的代码。我意识到，再次阅读您的问题，您可能会询问替代算法！）

于 2012-11-10T18:33:09.497 回答
0

您可以对相同长度的单词列表进行排序，然后进行 kind 的循环嵌套for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { }。

在 isSimilar 中计算差异，并在 2 上返回 false。

于 2012-11-10T18:43:53.910 回答