企业官网建设流程全解析

网站程序安装,免费做店招的网站,建站找哪个公司,什么网站专做店铺给定一个字符串数组 arr[]#xff0c;以及两个不同的字符串 start 和 target#xff0c;分别代表两个单词。任务是找到从字符串起始到目标的最短链条长度 #xff0c;使得相邻单词中仅 有一个字符不同#xff0c;且每个单词都存在于arr[]中。注意#xff1a;如果无法形成链…给定一个字符串数组 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, MapString, 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, ArrayListString arr) { MapString, 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(resultInteger.MAX_VALUE) result 0; return result; } public static void main(String[] args) { ArrayListString 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时间复杂度ON⋅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 SetString st new HashSetString(); 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 QueueString 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时间复杂度O26 * n * m * m On * m * m其中n是arr[]的大小m是每个单词的长度。辅助空间On * m编程资源 https://pan.quark.cn/s/7f7c83756948 更多资源 https://pan.quark.cn/s/bda57957c548