[Leetcode Solution] Word Ladder ii 2

GREAT PROBLEM with STRINGENT REQUIREMENT

Analysis

• Strive optimize my own BFS however still failed due to exceed time limits
• Some bloggers said by using unordered_map <string,vector<string>> to store the searching path which can significant improves the backtrack speed. However it does not
• The key is using unordered_set rather then queue to store the searching queue which can avoid the duplicated node being searching multiple times. The common sub problem should only be executed once which leads to pass the test case eventually
• This solution comes from this blog
• Using two unordered_set to store the current and next level of BFS searching node
• Once the end word appears in the next set, stop the search process and product the result
• Using a map to store the searching path because one word could be came from multiple words thus each word will be corresponding to multiple words by which to print the final result as well

Note

• how to avoid duplicated node visited many times by using set replaced vector to implement the queue
• how to backtrace the search result from bfs

Code

UPDATED AT LEETCODE 2ND PASS