我写了一个小程序,试图找到两个相等长度的英文单词之间的连接. Word A将通过一次更改一个字母转换为Word B,每个新创建的单词必须是英文单词.
例如：
Word A = BANG Word B = DUST
结果：
BANG -> BUNG ->BUNT -> DUNT -> DUST
我的过程：
>将英文单词列表(由109582个单词组成)加载到Map< Integer,List< String>> _wordMap = new HashMap();键将是字长.
>用户输入2个字.
> createGraph创建一个图.
>计算这2个节点之间的最短路径
>打印出结果.
一切工作都很好,但是对于步骤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的线程之后创建了这个.
