一种更有效的方法,可以找到彼此相同的英文单词

Question

我写了一个小程序,试图在两个相等长度的英语单词之间找到一个连接.单词A将通过一次更改一个字母转换为Word B,每个新创建的单词必须是英语单词.

例如:

Word A = BANG
Word B = DUST

结果:

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

我的过程:

1. 将一个英文单词列表(由109582个单词组成)加载到一个Map<Integer, List<String>> _wordMap = new HashMap();,键中将是单词长度.

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;
}

我的问题:

如何改进算法以加快进程？

对于正在阅读此内容的任何redditor,是的,我在昨天看到来自/ r/askreddit的帖子后创建了这个.

Answer 1

这是一个开始的想法:

创建一个Map<String, List<String>>(或者Multimap<String, String>如果你使用的是番石榴),并且对于每个单词,一次"删掉"一个字母,并将原始单词添加到该空白单词的列表中.所以你最终得到:

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

在这一点上,给出一个单词,你可以很容易地找到它所类似的所有单词 - 只需再次执行相同的过程,但不是添加到地图,只需获取每个"消隐"版本的所有值.