力扣面试题 17.22. 单词转换（java DFS解法）

Problem: 面试题 17.22. 单词转换

题目描述

思路

由于该题目涉及到所有的路径（可能），即我们可以想到利用DFS解法同时，题目只要求我们返回一条合法的路径即可，我们又可以在DFS的基础上利用回溯，具体到题目中:

1.我们对wodList中的每一个字符串进行DFS，为此我们可以定义一个HashSet（假设命名为visited）作为我们的一个辅助集合用于在DFS过程中判断是否遍历过，同时我们记录一个决策阶段（一个路径），将每次和法的阶段决策添加到路径中，同时每次判断是否进行下一阶段的DFS；
2.对于判断我们要额外编写一个判断函数（即当前单词和下一阶段待选单词是否只有一个字符不一样），再集合定义的辅助集合visited同时判断是否继续DFS
3.由于当前阶段可选的合法单词可能使用与另一条决策路径，所以我们每次递归结束后还需要将当前的决策路径恢复状态

解题方法

1.定义辅助HashSet集合visited，提前退出变量found（boolean类型），结果集合（也可以理解为一条合法路径）
2.编写判断两个字符串是否只有一个字符不同的函数isValidChange
3.编写dfs函数(dfs(String curWord, String endWord, List path, List wordList))

3.1 如果found为true则提前退出
3.2每阶段将当前合法的单词添加到路径path中，同时添加到辅助集合visited中
3.3判断如果当前的合法单词已经等于给定的单词endWord则将路径直接添加到结果集合中，并将foun设置为true
3.4判断若当前和法单词和wordList中的下一个待选单词不是只有一个字符不一样同时辅助集合visited中已经遍历过，则不继续DFS否则继续DFS
3.5每次将当前的路径中的最后一个值删去，达到恢复当前决策状态的操作

复杂度

时间复杂度:

最坏时间复杂度： $O(n^2)$ $n$为wordList数组的长度

空间复杂度:

$O(n)$

Code

class Solution {
    //Auxiliary set
    private Set<String> visited = new HashSet<>();
    //Result list
    private List<String> resultPath = new ArrayList<>();
    //Early exit condition
    private boolean found = false;

    /**
     * Returns a path to the word transformation
     *
     * @param beginWord Word to be transformed
     * @param endWord   Target word
     * @param wordList  String array
     * @return List<String>
     */
    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        dfs(beginWord, endWord, new ArrayList<>(), wordList);
        return resultPath;
    }

    /**
     * A transformation path is obtained by using DFS and backtracking
     *
     * @param curWord  Currently traversed word
     * @param endWord  Target word
     * @param path     Decision path
     * @param wordList String array
     */
    private void dfs(String curWord, String endWord, List<String> path, List<String> wordList) {
        //Early exit
        if (found) {
            return;
        }
        //Adds the current legal word to the path
        path.add(curWord);
        visited.add(curWord);
        //The same word as startWord has been found in wordList
        if (curWord.equals(endWord)) {
            resultPath.addAll(path);
            found = true;
            return;
        }
        for (int i = 0; i < wordList.size(); ++i) {
            String nextWord = wordList.get(i);
            if (visited.contains(nextWord) || !isValidChange(curWord, nextWord)) {
                continue;
            }
            dfs(nextWord, endWord, path, wordList);
        }
        //Restore current path
        path.remove(path.size() - 1);
    }

    /**
     * Determine if two words differ in only one character
     *
     * @param word1 Word to be compared
     * @param word2 Word to be compared
     * @return boolean
     */
    private boolean isValidChange(String word1, String word2) {
        int diff = 0;
        for (int i = 0; i < word1.length(); ++i) {
            if (word1.charAt(i) != word2.charAt(i)) {
                diff++;
            }
        }
        return diff == 1;
    }
}