java - 创建相差 1 个字符的单词图

Question

我有一个 map ，其中包含一个

• key = 单词的长度
• value = 包含该长度单词的数组列表

map 示例:

• [1] = a, [2] = at, in, it, an, ...

1.用户将输入wordA

2.用户将输入wordB

3.将检查两者是否相同

4.如果是，则将所有与wordA相差1个字母相邻的词作图。

5.那么那些与wordA相差一个字母的词将与与它们相差1个字母的词相邻。这样做直到到达 wordB。

如何制作图和邻接表？

我可以用什么来找到从 word1 到 word2 的路径。

谢谢， 费尔南多·迪亚兹

Answer 1

在构建从 word1 到 word2 的路径方面，这应该为您提供一些起点:

    public static List<String> findLadder(String word1, String word2) {
        //invalid request
        if (word1 == null || word2 == null || word1.length() != word2.length()) {
            return Collections.emptyList();
        }

        List<String> result = new ArrayList<String>();
        List<String> words = dictionary.get(word1.length());
        result.add(word1);

        while (! word1.equals(word2)) {
            String nextWord = null;
            for (int index = 0; index < word1.length(); index++) {
                if (word1.charAt(index) != word2.charAt(index)) {
                    String testWord = word1.substring(0, index) + word2.charAt(index) + word1.substring(index + 1);
                    if (words.contains(testWord)) { 
                        nextWord = testWord;
                        word1 = nextWord;
                        result.add(word1);
                        break;
                    }
                }
            }
            if (nextWord == null) {
                //no mapping exists
                return Collections.emptyList();
            }
        }

        return result;
    }

请注意，此代码不会评估任何不会逐渐接近所需输出的移动，例如从“代码”映射到“数据”时的 code -> core。评估这些举动是为了让你弄清楚。

此处示例:http://ideone.com/9JnNH