给定一个字符串数组 arr[]，以及两个不同的字符串 start 和 target，分别代表两个单词。任务是找到从字符串起始到目标的最短链条长度 ，使得相邻单词中仅 有一个字符不同，且每个单词都存在于arr[]中。
注意：如果无法形成链条，则打印0。arr[] 数组中的每个单词大小为 m，且仅包含小写英语字母表。
示例：
输入：开始 = “toon”，target = “plea”，arr[] = [“poon”， “plee”， “same”， “poie”， “plea”， “plie”， “poin”]
输出：7
解释：toon → poon → poin → poie → plie →plee → plea
输入： start = “abcv”， target = “ebad”， arr[] = [“abcd”， “ebad”， “ebcd”， “xyza”]
输出： 4
解释： abcv → abcd → ebcd → ebad
[天真方法]：利用回溯探索所有可能的路径
我们使用回溯来解决这个问题，因为它允许我们系统地探索从起始词到目标词的所有可能变换序列，同时确保不会在给定路径中重复访问同一个词。在每一步中，我们尝试当前单词中所有可能的单字母变化，如果生成的单词存在于词典中且尚未被访问，则递归进行。回溯使算法在到达死胡同或完成路径时“回溯”，然后尝试其他选项。
这在存在多条路径、需要找到最短有效变换序列的问题中尤为有用。虽然这种方法不是最优化的，但对于性能不是关键问题的小型数据集来说，它在概念上简单且有效。通过探索所有有效的变换路径，它保证在所有可能序列中找到最小步数。
import java.util.*; public class GfG { // Recursive function to find the shortest transformation chain public static int minWordTransform(String start, String target, Map<String, Integer> mp) { // If start word is the same as target, no transformation is needed if (start.equals(target)) return 1; int mini = Integer.MAX_VALUE; // Mark current word as visited mp.put(start, 1); // Try changing each character of the word for (int i = 0; i < start.length(); i++) { char[] chars = start.toCharArray(); char originalChar = chars[i]; // Try all possible lowercase letters at position i for (char ch = 'a'; ch <= 'z'; ch++) { chars[i] = ch; String transformed = new String(chars); // If the new word exists in dictionary and is not visited if (mp.containsKey(transformed) && mp.get(transformed) == 0) { // Recursive call for next transformation mini = Math.min(mini, 1 + minWordTransform(transformed, target, mp)); } } // Restore original character before moving to the next position chars[i] = originalChar; } // Mark current word as unvisited (backtracking) mp.put(start, 0); return mini; } // Wrapper function to prepare the map and call recursive function public static int wordLadder(String start, String target, ArrayList<String> arr) { Map<String, Integer> mp = new HashMap<>(); // Initialize all words from the dictionary as unvisited for (String word : arr) { mp.put(word, 0); } int result = minWordTransform(start, target, mp); if(result==Integer.MAX_VALUE) result = 0; return result; } public static void main(String[] args) { ArrayList<String> arr = new ArrayList<>(Arrays.asList( "poon", "plee", "same", "poie", "plie", "poin", "plea")); String start = "toon"; String target = "plea"; System.out.println(wordLadder(start, target, arr)); } }输出
6
时间复杂度：O（N⋅26L)），其中N是词典中的单词数，L是每个单词的长度。
空间复杂度：用于存储字典映射和递归调用栈，最坏情况下可达 N。
使用广度优先搜索
这个想法是用BFS找到起点和目标之间的最小链。为此，创建队列词来存储访问和 推入启动的词。在每个层级，逐一查看队列词中存储的所有元素，对每个元素，逐一更改其所有字符（a）为“z”，并检查新词是否在字典中。如果找到，将 新词推入队列，否则继续。每个队列层定义链条长度，一旦找到目标，返回该层的值 + 1。
import java.util.*; class GfG { static int wordLadder(String start, String target, String[] arr) { // Set to keep track of unvisited words Set<String> st = new HashSet<String>(); for(int i = 0; i < arr.length; i++) st.add(arr[i]); // Store the current chain length int res = 0; int m = start.length(); // Queue to store words to visit Queue<String> words = new LinkedList<>(); words.add(start); while (!words.isEmpty()) { int len = words.size(); res++; // Iterate through all words at the same level for (int i = 0; i < len; ++i) { String word = words.poll(); // For every character of the word for (int j = 0; j < m; ++j) { // Retain the original character // at the current position char[] wordArr = word.toCharArray(); char ch = wordArr[j]; // Replace the current character with // every possible lowercase alphabet for (char c = 'a'; c <= 'z'; ++c) { wordArr[j] = c; String newWord = new String(wordArr); // Skip the word if already added // or not present in set if (!st.contains(newWord)) continue; // If target word is found if (newWord.equals(target)) return res + 1; // Remove the word from set st.remove(newWord); // And push the newly generated word // which will be a part of the chain words.add(newWord); } // Restore the original character wordArr[j] = ch; } } } return 0; } public static void main(String[] args) { String[] arr = new String[]{"poon", "plee", "same", "poie", "plie", "poin", "plea"}; String start = "toon"; String target = "plea"; System.out.println(wordLadder(start, target, arr)); } }输出
7
时间复杂度：O（26 * n * m * m） = O（n * m * m），其中n是arr[]的大小，m是每个单词的长度。
辅助空间：O（n * m）
编程资源 https://pan.quark.cn/s/7f7c83756948 更多资源 https://pan.quark.cn/s/bda57957c548
