BFS traversal<\/a> and a HashSet to check whether a new word was present in the word list or not. The hashset is used to reduce the time complexity.<\/p>\n\n\n\nLet\u2019s understand it better with an example.<\/p>\n\n\n\n
Step: 1<\/strong> Enqueue the start word “rat” with a transformation length of 1, and Initialise the word set to [“bat”, “boy”, “bot”, “bog”].<\/p>\n\n\n\nStep: 2<\/strong> Dequeue “rat” (transformation length = 1). The key step involves generating one-letter transformations from the current word by changing the letter “r” to each letter from ‘a’ to ‘z’ and selecting words present in the word list.<\/p>\n\n\n\n
Since \u201cbat\u201d is present in the list, we can transform \u201crat\u201d to \u201cbat\u201d.<\/p>\n\n\n\n
Now, Enqueue “bat” with a transformation length of 2, and mark “bat” as visited by removing it from the word set.<\/p>\n\n\n\n
Step: 3<\/strong> Dequeue “bat” (transformation length = 2).<\/p>\n\n\n\n
Generate one-letter transformations: “bat” (ignore, as it’s the same as the current word), “bot”. <\/p>\n\n\n\n
Enqueue “bot” with a transformation length of 3, and mark “bot” as visited by removing it from the word set.<\/p>\n\n\n\n
Step: 4 <\/strong>Dequeue “bot” (transformation length = 3).<\/p>\n\n\n\n
Generate one-letter transformations: “bot” (ignore), “bat” (ignore), “hot”, …, “bot” (ignore).<\/p>\n\n\n\n
Enqueue “bog” with a transformation length of 4. Mark “bog” as visited by removing it from the word set.<\/p>\n\n\n\n
Step: 5 <\/strong>Dequeue “bog” (transformation length = 4).<\/p>\n\n\n\n
The target word “bog” is reached, and the transformation length is 4.<\/p>\n\n\n\n
Return the transformation length, which is 4.<\/p>\n\n\n\n
C++ Code<\/strong><\/h3>\n\n\n\nHere is the C++ program to solve the Word Ladder problem:<\/p>\n\n\n\n
#include <iostream>\n#include <vector>\n#include <queue>\n#include <unordered_set>\n\nusing namespace std;\n\nclass Solution {\npublic:\n int wordLadderLength(string startword, string targetword, vector<string>& wordlist) {\n queue<pair<string, int>> q;\n q.push({startword, 1});\n\n \/\/ Using an unordered_set for O(1) word existence check and removal\n unordered_set<string> st(wordlist.begin(), wordlist.end());\n \n \t\/\/ Remove the start word from the set\n st.erase(startword); \n\n while (!q.empty()) {\n string word = q.front().first;\n int steps = q.front().second;\n q.pop();\n\n if (word == targetword) {\n return steps;\n }\n\n \/\/ Generate one-letter transformations of the current word\n for (int i = 0; i < word.size(); i++) {\n char original = word[i];\n\n for (char ch = 'a'; ch <= 'z'; ch++) {\n word[i] = ch;\n\n if (st.find(word) != st.end()) {\n \/\/ If the transformed word is in the set, remove it and enqueue\n st.erase(word);\n q.push({word, steps + 1});\n }\n }\n\n \/\/ Restore the original character at position I\n word[i] = original;\n }\n }\n\t\t\n \t\/\/ If no transformation found\n return 0; \n }\n};\n\nint main() {\n Solution solution;\n \n string startWord = "rat";\n string endWord = "bog";\n vector<string> wordList = {"bat", "boy", "bot", "bog"};\n\n int result = solution.wordLadderLength(startWord, endWord, wordList);\n\n if (result > 0) {\n cout << "Shortest word ladder length: " << result << endl;\n } \n \telse {\n cout << "No transformation sequence found." << endl;\n }\n\n return 0;\n}<\/pre><\/div>\n\n\n\nPython Code<\/strong><\/h3>\n\n\n\nBelow is the Python program for the BFS approach to solve Word Ladder problem:<\/p>\n\n\n\n
from collections import deque\n\nclass Solution:\n def word_ladder_length(self, start_word, target_word, word_list):\n q = deque([(start_word, 1)])\n st = set(word_list)\n # Remove the start word from the set\n st.discard(start_word) \n\n while q:\n word, steps = q.popleft()\n\n if word == target_word:\n return steps\n\n # Generate one-letter transformations of the current word\n for i in range(len(word)):\n original = word[i]\n for ch in 'abcdefghijklmnopqrstuvwxyz':\n \t# Generate a new word\n new_word = word[:i] + ch + word[i+1:] \n if new_word in st:\n # If the transformed word is in the set, remove it and enqueue\n st.remove(new_word)\n q.append((new_word, steps + 1))\n\n # Restore the original character at position i\n word = word[:i] + original + word[i+1:]\n \n\t\t# If no transformation found\n return 0 \n\n\nif __name__ == "__main__":\n solution = Solution()\n\n start_word = "rat"\n end_word = "bog"\n word_list = ["bat", "boy", "bot", "bog"]\n\n result = solution.word_ladder_length(start_word, end_word, word_list)\n\n if result > 0:\n print("Shortest word ladder length:", result)\n else:\n print("No transformation sequence found.")\n<\/pre><\/div>\n\n\n\nJava Code<\/strong><\/h3>\n\n\n\nYou can the Java program below for Word Ladder:<\/p>\n\n\n\n
import java.util.*;\n\nclass Solution {\n public int wordLadderLength(String startWord, String targetWord, List<String> wordList) {\n Queue<Map.Entry<String, Integer>> q = new LinkedList<>();\n q.offer(new AbstractMap.SimpleEntry<>(startWord, 1));\n\n Set<String> wordSet = new HashSet<>(wordList);\n \t\/\/ Remove the start word from the set\n wordSet.remove(startWord); \n\n while (!q.isEmpty()) {\n Map.Entry<String, Integer> current = q.poll();\n String word = current.getKey();\n int steps = current.getValue();\n\n if (word.equals(targetWord)) {\n return steps;\n }\n\n \/\/ Generate one-letter transformations of the current word\n for (int i = 0; i < word.length(); i++) {\n char[] chars = word.toCharArray();\n char original = chars[i];\n\n for (char ch = 'a'; ch <= 'z'; ch++) {\n chars[i] = ch;\n String transformedWord = new String(chars);\n\n if (wordSet.contains(transformedWord)) {\n \/\/ If the transformed word is in the set, remove it and enqueue\n wordSet.remove(transformedWord);\n q.offer(new AbstractMap.SimpleEntry<>(transformedWord, steps + 1));\n }\n }\n\n \/\/ Restore the original character at position i\n chars[i] = original;\n }\n }\n\t\t\/\/ If no transformation found\n return 0; \n }\n\n public static void main(String[] args) {\n Solution solution = new Solution();\n\n String startWord = "rat";\n String endWord = "bog";\n List<String> wordList = Arrays.asList("bat", "boy", "bot", "bog");\n\n int result = solution.wordLadderLength(startWord, endWord, wordList);\n\n if (result > 0) {\n System.out.println("Shortest word ladder length: " + result);\n } else {\n System.out.println("No transformation sequence found.");\n }\n }\n}<\/pre><\/div>\n\n\n\nOutput:<\/strong><\/p>\n\n\n\nShortest word ladder length: 4<\/code><\/pre>\n\n\n\nComplexity Analysis<\/strong><\/h3>\n\n\n\nThe time complexity of the Word Ladder solution is O(N * M * 26)<\/strong>, where N represents the size of the word list array, and M denotes the word length of the words present in the word list. It’s important to note that the constant factor 26 is attributed to the number of characters in the alphabet.<\/p>\n\n\n\nThe space complexity is O(N), encompassing the creation of an unordered set and the storage of all values from the wordList array. This space complexity accounts for the memory required for efficient traversal and storage during the execution of the algorithm.<\/p>\n\n\n\n
Conclusion<\/strong><\/h2>\n\n\n\nIn summary, the Word Ladder problem is a creative challenge with practical applications in natural language processing, spell check and autocorrection systems, and genetic algorithms. We used the BFS traversal approach to solve this problem with the time complexity O(N * M * 26), where N is the size of the word list, and M is the word length.<\/p>\n","protected":false},"excerpt":{"rendered":"
Understand the word ladder programming problem from leetcode and get the solution in C++, Java, and Python.<\/p>\n","protected":false},"author":12,"featured_media":353,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[29,14,15],"class_list":["post-346","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-bfs","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/346","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=346"}],"version-history":[{"count":3,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/346\/revisions"}],"predecessor-version":[{"id":419,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/346\/revisions\/419"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/353"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=346"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=346"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=346"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"Example](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/0-1024x576.png\")
<\/figure>\n<\/div>\n\n\n![\"Step:2](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/1-1-1-1024x407.png\")
<\/figure>\n<\/div>\n\n\n![\"step](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/2-2-1024x389.png\")
<\/figure>\n<\/div>\n\n\n![\"Step:](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/3-2-1024x450.png\")
<\/figure>\n<\/div>\n\n\n![\"Step:](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/11\/4-2-1024x293.png\")
<\/figure>\n<\/div>\n\n\n