Category Archives: Graph

Word Ladder II

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 [ … Continue reading

Posted in Graph, Hashtable and Map, Stack and Queue | Leave a comment

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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”] … Continue reading

Posted in Graph, Stack and Queue, String | Leave a comment

Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’, capture all regions surrounded by ‘X’. A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region . For example, X X X X X O O X X X O X X O X … Continue reading

Posted in Graph, Stack and Queue | Leave a comment

Clone Graph I

Clone a graph. Input is a Node pointer. Return the Node pointer of the cloned graph. A graph is defined below: struct Node { vector<Node *> neighbors; } Idea: Bread First Search. Difficulties: How to identify visited nodes. Otherwise, cycles … Continue reading

Posted in Graph, Hashtable and Map | Leave a comment