Problem

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

 Notice

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

Example
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

思路(DFS, TLE)

1. 每一个transformation path 相当于一个permutation
2. 所以当前递归需要得出下个transformation, 于是有 25 * string.length() 种可能,
3. 并且需要一个set来标记访问过的元素

    private int minTrans;
    public int ladderLength(String start, String end, Set<String> dict) {
        if (start.length() != end.length() || end.length() <= 0) return 0;
        dict.add(end);
        minTrans = Integer.MAX_VALUE;
        helper(start, end, new HashSet<String>(), dict, 1);
        return minTrans == Integer.MAX_VALUE ? 0 : minTrans;
    }

    private void helper(String s, String target, Set<String> visited, Set<String> dict, int trans) {
        if (s.equals(target)) {
            minTrans = Math.min(minTrans, trans);
            return;
        }

        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (arr[i] == c) continue;
                char original = arr[i];
                arr[i] = c;
                String newS = String.valueOf(arr);
                trans++;
                if (!visited.contains(newS) && dict.contains(newS)) {
                    visited.add(newS);
                    helper(newS, target, visited, dict, trans);
                    visited.remove(newS);
                }
                trans--;
                arr[i] = original;
            }
        }
    }