<
8045
script type="application/json" data-target="react-app.embeddedData">{"payload":{"allShortcutsEnabled":false,"fileTree":{"src/wordLadder":{"items":[{"name":"wordLadder.II.cpp","path":"src/wordLadder/wordLadder.II.cpp","contentType":"file"},{"name":"wordLadder.cpp","path":"src/wordLadder/wordLadder.cpp","contentType":"file"}],"totalCount":2},"src":{"items":[{"name":"3Sum","path":"src/3Sum","contentType":"directory"},{"name":"3SumClosest","path":"src/3SumClosest","contentType":"directory"},{"name":"4Sum","path":"src/4Sum","contentType":"directory"},{"name":"LRUCache","path":"src/LRUCache","contentType":"directory"},{"name":"addBinary","path":"src/addBinary","contentType":"directory"},{"name":"addTwoNumbers","path":"src/addTwoNumbers","contentType":"directory"},{"name":"anagrams","path":"src/anagrams","contentType":"directory"},{"name":"balancedBinaryTree","path":"src/balancedBinaryTree","contentType":"directory"},{"name":"bestTimeToBuyAndSellStock","path":"src/bestTimeToBuyAndSellStock","contentType":"directory"},{"name":"binaryTreeInorderTraversal","path":"src/binaryTreeInorderTraversal","contentType":"directory"},{"name":"binaryTreeLevelOrderTraversal","path":"src/binaryTreeLevelOrderTraversal","contentType":"directory"},{"name":"binaryTreeMaximumPathSum","path":"src/binaryTreeMaximumPathSum","contentType":"directory"},{"name":"binaryTreePostorderTraversal","path":"src/binaryTreePostorderTraversal","contentType":"directory"},{"name":"binaryTreePreorderTraversal","path":"src/binaryTreePreorderTraversal","contentType":"directory"},{"name":"binaryTreeZigzagLevelOrderTraversal","path":"src/binaryTreeZigzagLevelOrderTraversal","contentType":"directory"},{"name":"candy","path":"src/candy","contentType":"directory"},{"name":"climbStairs","path":"src/climbStairs","contentType":"directory"},{"name":"cloneGraph","path":"src/cloneGraph","contentType":"directory"},{"name":"combinationSum","path":"src/combinationSum","contentType":"directory"},{"name":"combinations","path":"src/combinations","contentType":"directory"},{"name":"constructBinaryTreeFromInorderAndPostorderTraversal","path":"src/constructBinaryTreeFromInorderAndPostorderTraversal","contentType":"directory"},{"name":"constructBinaryTreeFromPreorderAndInorderTraversal","path":"src/constructBinaryTreeFromPreorderAndInorderTraversal","contentType":"directory"},{"name":"containerWithMostWater","path":"src/containerWithMostWater","contentType":"directory"},{"name":"convertSortedArrayToBinarySearchTree","path":"src/convertSortedArrayToBinarySearchTree","contentType":"directory"},{"name":"convertSortedListToBinarySearchTree","path":"src/convertSortedListToBinarySearchTree","contentType":"directory"},{"name":"copyListWithRandomPointer","path":"src/copyListWithRandomPointer","contentType":"directory"},{"name":"countAndSay","path":"src/countAndSay","contentType":"directory"},{"name":"decodeWays","path":"src/decodeWays","contentType":"directory"},{"name":"distinctSubsequences","path":"src/distinctSubsequences","contentType":"directory"},{"name":"divideTwoInt","path":"src/divideTwoInt","contentType":"directory"},{"name":"editDistance","path":"src/editDistance","contentType":"directory"},{"name":"evaluateReversePolishNotation","path":"src/evaluateReversePolishNotation","contentType":"directory"},{"name":"findMinimumInRotatedSortedArray","path":"src/findMinimumInRotatedSortedArray","contentType":"directory"},{"name":"firstMissingPositive","path":"src/firstMissingPositive","contentType":"directory"},{"name":"flattenBinaryTreeToLinkedList","path":"src/flattenBinaryTreeToLinkedList","contentType":"directory"},{"name":"gasStation","path":"src/gasStation","contentType":"directory"},{"name":"generateParentheses","path":"src/generateParentheses","contentType":"directory"},{"name":"grayCode","path":"src/grayCode","contentType":"directory"},{"name":"insertInterval","path":"src/insertInterval","contentType":"directory"},{"name":"insertionSortList","path":"src/insertionSortList","contentType":"directory"},{"name":"integerToRoman","path":"src/integerToRoman","contentType":"directory"},{"name":"interleavingString","path":"src/interleavingString","contentType":"directory"},{"name":"jumpGame","path":"src/jumpGame","contentType":"directory"},{"name":"largestRectangleInHistogram","path":"src/largestRectangleInHistogram","contentType":"directory"},{"name":"lengthOfLastWord","path":"src/lengthOfLastWord","contentType":"directory"},{"name":"letterCombinationsOfAPhoneNumber","path":"src/letterCombinationsOfAPhoneNumber","contentType":"directory"},{"name":"linkedListCycle","path":"src/linkedListCycle","contentType":"directory"},{"name":"longestCommonPrefix","path":"src/longestCommonPrefix","contentType":"directory"},{"name":"longestConsecutiveSequence","path":"src/longestConsecutiveSequence","contentType":"directory"},{"name":"longestPalindromicSubstring","path":"src/longestPalindromicSubstring","contentType":"directory"},{"name":"longestSubstringWithoutRepeatingCharacters","path":"src/longestSubstringWithoutRepeatingCharacters","contentType":"directory"},{"name":"longestValidParentheses","path":"src/longestValidParentheses","contentType":"directory"},{"name":"maxPointsOnALine","path":"src/maxPointsOnALine","contentType":"directory"},{"name":"maximalRectangle","path":"src/maximalRectangle","contentType":"directory"},{"name":"maximumDepthOfBinaryTree","path":"src/maximumDepthOfBinaryTree","contentType":"directory"},{"name":"maximumProductSubarray","path":"src/maximumProductSubarray","contentType":"directory"},{"name":"maximumSubArray","path":"src/maximumSubArray","contentType":"directory"},{"name":"medianOfTwoSortedArrays","path":"src/medianOfTwoSortedArrays","contentType":"directory"},{"name":"mergeIntervals","path":"src/mergeIntervals","contentType":"directory"},{"name":"mergeKSortedLists","path":"src/mergeKSortedLists","contentType":"directory"},{"name":"mergeTwoSortedArray","path":"src/mergeTwoSortedArray","contentType":"directory"},{"name":"mergeTwoSortedList","path":"src/mergeTwoSortedList","contentType":"directory"},{"name":"minimumDepthOfBinaryTree","path":"src/minimumDepthOfBinaryTree","contentType":"directory"},{"name":"minimumPathSum","path":"src/minimumPathSum","contentType":"directory"},{"name":"minimumWindowSubstring","path":"src/minimumWindowSubstring","contentType":"directory"},{"name":"multiplyStrings","path":"src/multiplyStrings","contentType":"directory"},{"name":"nQueens","path":"src/nQueens","contentType":"directory"},{"name":"nextPermutation","path":"src/nextPermutation","contentType":"directory"},{"name":"palindromeNumber","path":"src/palindromeNumber","contentType":"directory"},{"name":"palindromePartitioning","path":"src/palindromePartitioning","contentType":"directory"},{"name":"partitionList","path":"src/partitionList","contentType":"directory"},{"name":"pascalTriangle","path":"src/pascalTriangle","contentType":"directory"},{"name":"pathSum","path":"src/pathSum","contentType":"directory"},{"name":"permutationSequence","path":"src/permutationSequence","contentType":"directory"},{"name":"permutations","path":"src/permutations","contentType":"directory"},{"name":"plusOne","path":"src/plusOne","contentType":"directory"},{"name":"populatingNextRightPointersInEachNode","path":"src/populatingNextRightPointersInEachNode","contentType":"directory"},{"name":"pow","path":"src/pow","contentType":"directory"},{"name":"recoverBinarySearchTree","path":"src/recoverBinarySearchTree","contentType":"directory"},{"name":"regularExpressionMatching","path":"src/regularExpressionMatching","contentType":"directory"},{"name":"removeDuplicatesFromSortedArray","path":"src/removeDuplicatesFromSortedArray","contentType":"directory"},{"name":"removeDuplicatesFromSortedList","path":"src/removeDuplicatesFromSortedList","contentType":"directory"},{"name":"removeElement","path":"src/removeElement","contentType":"directory"},{"name":"removeNthNodeFromEndOfList","path":"src/removeNthNodeFromEndOfList","contentType":"directory"},{"name":"reorderList","path":"src/reorderList","contentType":"directory"},{"name":"restoreIPAddresses","path":"src/restoreIPAddresses","contentType":"directory"},{"name":"reverseInteger","path":"src/reverseInteger","contentType":"directory"},{"name":"reverseLinkedList","path":"src/reverseLinkedList","contentType":"directory"},{"name":"reverseNodesInKGroup","path":"src/reverseNodesInKGroup","contentType":"directory"},{"name":"reverseWordsInAString","path":"src/reverseWordsInAString","contentType":"directory"},{"name":"romanToInteger","path":"src/romanToInteger","contentType":"directory"},{"name":"rotateImage","path":"src/rotateImage","contentType":"directory"},{"name":"rotateList","path":"src/rotateList","contentType":"directory"},{"name":"sameTree","path":"src/sameTree","contentType":"directory"},{"name":"scrambleString","path":"src/scrambleString","contentType":"directory"},{"name":"search2DMatrix","path":"src/search2DMatrix","contentType":"directory"},{"name":"searchForRange","path":"src/searchForRange","contentType":"directory"},{"name":"searchInRotatedSortedArray","path":"src/searchInRotatedSortedArray","contentType":"directory"},{"name":"searchInsertPosition","path":"src/searchInsertPosition","contentType":"directory"},{"name":"setMatrixZeroes","path":"src/setMatrixZeroes","contentType":"directory"},{"name":"simplifyPath","path":"src/simplifyPath","contentType":"directory"},{"name":"singleNumber","path":"src/singleNumber","contentType":"directory"},{"name":"sortColors","path":"src/sortColors","contentType":"directory"},{"name":"sortList","path":"src/sortList","contentType":"directory"},{"name":"spiralMatrix","path":"src/spiralMatrix","contentType":"directory"},{"name":"sqrt","path":"src/sqrt","contentType":"directory"},{"name":"strStr","path":"src/strStr","contentType":"directory"},{"name":"stringToIntegerAtoi","path":"src/stringToIntegerAtoi","contentType":"directory"},{"name":"subsets","path":"src/subsets","contentType":"directory"},{"name":"substringWithConcatenationOfAllWords","path":"src/substringWithConcatenationOfAllWords","contentType":"directory"},{"name":"sudokuSolver","path":"src/sudokuSolver","contentType":"directory"},{"name":"sumRootToLeafNumber","path":"src/sumRootToLeafNumber","contentType":"directory"},{"name":"surroundedRegions","path":"src/surroundedRegions","contentType":"directory"},{"name":"swapNodesInPairs","path":"src/swapNodesInPairs","contentType":"directory"},{"name":"symmetricTree","path":"src/symmetricTree","contentType":"directory"},{"name":"textJustification","path":"src/textJustification","contentType":"directory"},{"name":"trappingRainWater","path":"src/trappingRainWater","contentType":"directory"},{"name":"triangle","path":"src/triangle","contentType":"directory"},{"name":"twoSum","path":"src/twoSum","contentType":"directory"},{"name":"uniqueBinarySearchTrees","path":"src/uniqueBinarySearchTrees","contentType":"directory"},{"name":"uniquePaths","path":"src/uniquePaths","contentType":"directory"},{"name":"validNumber","path":"src/validNumber","contentType":"directory"},{"name":"validPalindrome","path":"src/validPalindrome","contentType":"directory"},{"name":"validParentheses","path":"src/validParentheses","contentType":"directory"},{"name":"validSudoku","path":"src/validSudoku","contentType":"directory"},{"name":"validateBinarySearchTree","path":"src/validateBinarySearchTree","contentType":"directory"},{"name":"wildcardMatching","path":"src/wildcardMatching","contentType":"directory"},{"name":"wordBreak","path":"src/wordBreak","contentType":"directory"},{"name":"wordLadder","path":"src/wordLadder","contentType":"directory"},{"name":"wordSearch","path":"src/wordSearch","contentType":"directory"},{"name":"zigZagConversion","path":"src/zigZagConversion","contentType":"directory"}],"totalCount":131},"":{"items":[{"name":"src","path":"src","contentType":"directory"},{"name":"README.md","path":"README.md","contentType":"file"}],"totalCount":2}},"fileTreeProcessingTime":10.887041,"foldersToFetch":[],"incompleteFileTree":false,"repo":{"id":25857062,"defaultBranch":"master","name":"leetcode","ownerLogin":"miffa","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2014-10-28T07:03:30.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/4045546?v=4","public":true,"private":false,"isOrgOwned":false},"codeLineWrapEnabled":false,"symbolsExpanded":false,"treeExpanded":true,"refInfo":{"name":"master","listCacheKey":"v0:1615741789.119309","canEdit":false,"refType":"branch","currentOid":"540738b55bfdc49eba05ed8dce45631e3758ba1b"},"path":"src/wordLadder/wordLadder.II.cpp","currentUser":null,"blob":{"rawLines":["// Source : https://oj.leetcode.com/problems/word-ladder-ii/","// Author : Hao Chen","// Date : 2014-10-13","","/********************************************************************************** ","* ","* Given two words (start and end), and a dictionary, find all shortest transformation ","* sequence(s) from start to end, such that:","* ","* Only one letter can be changed at a time","* Each intermediate word must exist in the dictionary","* ","* For example,","* ","* Given:","* start = \"hit\"","* end = \"cog\"","* dict = [\"hot\",\"dot\",\"dog\",\"lot\",\"log\"]","* ","* Return","* ","* [","* [\"hit\",\"hot\",\"dot\",\"dog\",\"cog\"],","* [\"hit\",\"hot\",\"lot\",\"log\",\"cog\"]","* ]","* ","* Note:","* ","* All words have the same length.","* All words contain only lowercase alphabetic characters.","* ","* ","**********************************************************************************/","","#include \u003ciostream\u003e","#include \u003cvector\u003e","#include \u003cmap\u003e","#include \u003cqueue\u003e","#include \u003cunordered_set\u003e","using namespace std;","","// Solution","//","// 1) Using BSF algorithm build a tree like below","// 2) Using DSF to parse the tree to the transformation path.","//","// For example:","//","// start = \"hit\"","// end = \"cog\"","// dict = [\"hot\",\"dot\",\"dog\",\"lot\",\"log\",\"dit\",\"hig\", \"dig\"]","//","// +-----+","// +-------------+ hit +--------------+","// | +--+--+ |","// | | |","// +--v--+ +--v--+ +--v--+","// | dit | +-----+ hot +---+ | hig |","// +--+--+ | +-----+ | +--+--+","// | | | |","// | +--v--+ +--v--+ +--v--+","// +----\u003e dot | | lot | | dig |","// +--+--+ +--+--+ +--+--+","// | | |","// +--v--+ +--v--+ |","// +----\u003e dog | | log | |","// | +--+--+ +--+--+ |","// | | | |","// | | +--v--+ | |","// | +---\u003e| cog |\u003c-- + |","// | +-----+ |","// | |","// | |","// +----------------------------------+","","map\u003c string, unordered_set\u003cstring\u003e \u003e\u0026 ","buildTree(string\u0026 start, string\u0026 end, unordered_set\u003cstring\u003e \u0026dict) {",""," static map\u003c string, unordered_set\u003cstring\u003e \u003e parents;"," parents.clear();",""," unordered_set\u003cstring\u003e level[3];"," unordered_set\u003cstring\u003e *previousLevel = \u0026level[0];"," unordered_set\u003cstring\u003e *currentLevel = \u0026level[1];"," unordered_set\u003cstring\u003e *newLevel = \u0026level[2];"," unordered_set\u003cstring\u003e *p =NULL;"," currentLevel-\u003einsert(start);",""," bool reachEnd = false;",""," while( !reachEnd ) {"," newLevel-\u003eclear();"," for(auto it=currentLevel-\u003ebegin(); it!=currentLevel-\u003eend(); it++) { "," for (int i=0; i\u003cit-\u003esize(); i++) {"," string newWord = *it;"," for(char c='a'; c\u003c='z'; c++){"," newWord[i] = c;"," if (newWord == end){"," reachEnd = true;"," parents[*it].insert(end);"," continue;"," }"," if ( dict.count(newWord)==0 || currentLevel-\u003ecount(newWord)\u003e0 || previousLevel-\u003ecount(newWord)\u003e0 ) {"," continue;"," }"," newLevel-\u003einsert(newWord);"," //parents[newWord].insert(*it);"," parents[*it].insert(newWord);"," }"," }"," } "," if (newLevel-\u003eempty()) break;",""," p = previousLevel; "," previousLevel = currentLevel;"," currentLevel = newLevel;"," newLevel = p;"," }","",""," if ( !reachEnd ) {"," parents.clear();"," } "," return parents;","}","","void generatePath( string start, string end,"," map\u003c string, unordered_set\u003cstring\u003e \u003e \u0026parents, "," vector\u003cstring\u003e path,"," vector\u003c vector\u003cstring\u003e \u003e \u0026paths) {",""," if (parents.find(start) == parents.end()){"," if (start == end){"," paths.push_back(path);"," }"," return;"," }",""," for(auto it=parents[start].begin(); it!=parents[start].end(); it++){"," path.push_back(*it);"," generatePath(*it, end, parents, path, paths);"," path.pop_back();"," }","","}","","vector\u003c vector\u003cstring\u003e \u003e ","findLadders(string start, string end, unordered_set\u003cstring\u003e \u0026dict) {",""," vector\u003c vector\u003cstring\u003e \u003e ladders;"," vector\u003cstring\u003e ladder;"," ladder.push_back(start);"," if (start == end){"," ladder.push_back(end);"," ladders.push_back(ladder);"," return ladders;"," }",""," map\u003c string, unordered_set\u003cstring\u003e \u003e\u0026 parents = buildTree(start, end, dict);",""," if (parents.size()\u003c=0) {"," return ladders;"," }",""," generatePath(start, end, parents, ladder, ladders);",""," return ladders;","}","","void printLadders(vector\u003c vector\u003cstring\u003e \u003e \u0026ladders){"," int i, j;"," for (i=0; i\u003cladders.size(); i++){"," for (j=0; j\u003cladders[i].size()-1; j++){"," cout \u003c\u003c ladders[i][j] \u003c\u003c \" -\u003e \";"," }"," cout \u003c\u003c ladders[i][j] \u003c\u003c endl; "," }","}","","int main(int argc, char** argv)","{"," string start = \"hit\";"," string end = \"cog\";"," //unordered_set\u003cstring\u003e dict ({\"hot\",\"dot\",\"dog\",\"lot\",\"log\"});"," unordered_set\u003cstring\u003e dict ({\"bot\",\"cig\", \"cog\", \"dit\", \"dut\", \"hot\", \"hit\" ,\"dot\",\"dog\",\"lot\",\"log\"});",""," vector\u003c vector\u003cstring\u003e \u003e ladders;"," ladders = findLadders(start, end, dict);"," printLadders(ladders);"," return 0;","}"],"stylingDirectives":null,"colorizedLines":null,"csv":null,"csvError":null,"dependabotInfo":{"showConfigurationBanner":false,"configFilePath":null,"networkDependabotPath":"/miffa/leetcode/network/updates","dismissConfigurationNoticePath":"/settings/dismiss-notice/dependabot_configuration_notice","configurationNoticeDismissed":null},"displayName":"wordLadder.II.cpp","displayUrl":"https://github.com/miffa/leetcode/blob/master/src/wordLadder/wordLadder.II.cpp?raw=true","headerInfo":{"blobSize":"5.4 KB","deleteTooltip":"You must be signed in to make or propose changes","editTooltip":"You must be signed in to make or propose changes","ghDesktopPath":"https://desktop.github.com","isGitLfs":false,"onBranch":true,"shortPath":"79d4e07","siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fmiffa%2Fleetcode%2Fblob%2Fmaster%2Fsrc%2FwordLadder%2FwordLadder.II.cpp","isCSV":false,"isRichtext":false,"toc":null,"lineInfo":{"truncatedLoc":"191","truncatedSloc":"167"},"mode":"file"},"image":false,"isCodeownersFile":null,"isPlain":false,"isValidLegacyIssueTemplate":false,"issueTemplate":null,"discussionTemplate":null,"language":"C++","languageID":43,"large":false,"planSupportInfo":{"repoIsFork":null,"repoOwnedByCurrentUser":null,"requestFullPath":"/miffa/leetcode/blob/master/src/wordLadder/wordLadder.II.cpp","showFreeOrgGatedFeatureMessage":null,"showPlanSupportBanner":null,"upgradeDataAttributes":null,"upgradePath":null},"publishBannersInfo":{"dismissActionNoticePath":"/settings/dismiss-notice/publish_action_from_dockerfile","releasePath":"/miffa/leetcode/releases/new?marketplace=true","showPublishActionBanner":false},"rawBlobUrl":"https://github.com/miffa/leetcode/raw/refs/heads/master/src/wordLadder/wordLadder.II.cpp","renderImageOrRaw":false,"richText":null,"renderedFileInfo":null,"shortPath":null,"symbolsEnabled":true,"tabSize":8,"topBannersInfo":{"overridingGlobalFundingFile":false,"globalPreferredFundingPath":null,"showInvalidCitationWarning":false,"citationHelpUrl":"https://docs.github.com/github/creating-cloning-and-archiving-repositories/creating-a-repository-on-github/about-citation-files","actionsOnboardingTip":null},"truncated":false,"viewable":true,"workflowRedirectUrl":null,"symbols":null},"copilotInfo":null,"copilotAccessAllowed":false,"modelsAccessAllowed":false,"modelsRepoIntegrationEnabled":false,"csrf_tokens":{"/miffa/leetcode/branches":{"post":"au6ABrSUx2eG-yhprf9qLFQQS-QM0O1BxUtzNSxzKwEKjGDqwNftcEcpfBVgqxHrVDBSliudpGDcZkvC4TCNBQ"},"/repos/preferences":{"post":"4k0X8HmRCaLAUsbyGu5uNo5jqkWwIoA0xcuB9CGrlQtBAtgPDv6TTJcSkcSejUWj1myM22FZmoM1ImBIW0x78Q"}}},"title":"leetcode/src/wordLadder/wordLadder.II.cpp at master · miffa/leetcode","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-1b17b3e7786a.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}
You can’t perform that action at this time.