Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Solution: treat each cell as a node of a graph, and its four cells (up, down, left, right) as neighbors. Use DFS, and use a visited array to mark if a node has been already visited. Starting a DFS from every cell of the board. If find, return true.

Java语言: WordSearch

01 public boolean exist(char[][] board, String word) {
02     int numRows=board.length;
03     int numCols=board[0].length;      
04     boolean [][]visited=new boolean[numRows][numCols];
05     for(int i=0;i<numRows;i++)
06     {
07         for(int j=0;j<numCols;j++)
08         {
09             //DFS starting from each cell
10             if(exist(board, i, j, 0, visited, word))
11                 return true;
12             //reset visited    
13             visited=new boolean[numRows][numCols];
14         }
15     }
16     return false;
17 }
18 
19 //DFS for substring starting at position i of word
20 public boolean exist(char[][] board, int row, int col, int i, boolean[][]visited, String word)
21 {
22     if(i==word.length())
23     {
24         return true;
25     }
26     if(row<0||row>=board.length||col<0 || col>=board[0].length)
27     {
28         return false;
29     }
30     if(!visited[row][col])
31     {
32         //set the current position of board as visited
33         if(board[row][col]==word.charAt(i))
34         {
35             visited[row][col]=true;
36             //DFS on its four neighbor
37             boolean case1=exist(board, row+1, col, i+1, visited, word);
38             boolean case2=exist(board, row-1, col, i+1, visited, word);
39             boolean case3=exist(board, row, col+1, i+1, visited, word);
40             boolean case4=exist(board, row, col-1, i+1, visited, word);              
41             return case1||case2||case3||case4;              
42         }          
43     }
44     return false;
45 }

Clone a Graph

Clone a graph. Input is a Node pointer. Return the Node pointer of the cloned graph.

Assume that a graph is represented as,

Java语言: GraphNode

1 public class GraphNode {
2     int value;
3     ArrayList<GraphNode> neighbors;
4     public GraphNode(int value)
5     {
6         this.value=value;
7         neighbors=new ArrayList<GraphNode>();
8     }
9 }

This question can be done by both BFS and DFS. Let's look at BFS first. Remember to use a hash table to record the nodes you have already copied.

Java语言: CloneAGraph

01 public GraphNode cloneBFS(GraphNode g)
02 {
03     //This hash table maps an original node to its copy in the new graph
04     Hashtable<GraphNode,GraphNode> copy_table=new Hashtable<GraphNode,GraphNode>();
05     //Queue of BFS
06     LinkedList<GraphNode> queue=new LinkedList<GraphNode>();
07     //copy the very first node
08     GraphNode g_copy=new GraphNode(g.value);
09     //put already copied node to the hash table
10     copy_table.put(g, g_copy);  
11     //start BFS traversal
12     queue.add(g);
13     while(queue.size()!=0)
14     {
15         GraphNode curr_node=queue.remove();          
16         for(GraphNode neighbor:curr_node.neighbors)
17         {  
18             //neighbor node not copied before, can be seen as a child node
19             if(!copy_table.containsKey(neighbor))
20             {  
21                 //clone this neighbor
22                 GraphNode child_copy=new GraphNode(neighbor.value);
23               
24                 //get the copy of the current node
25                 //assign the child node copy to the
26                 //current node copy's adjacent list
27                 GraphNode curr_node_copy=copy_table.get(curr_node);
28                 curr_node_copy.neighbors.add(child_copy);
29               
30                 //update the copy table by inserting
31                 //the new original and copy pairs
32                 copy_table.put(neighbor, child_copy);
33                 queue.add(neighbor);
34             }
35             else //met a parent node
36             {  
37                 //get the copy of the parent node
38                 GraphNode parent_copy=copy_table.get(neighbor);
39                 //get the copy of the current node itself
40                 GraphNode curr_node_copy=copy_table.get(curr_node);
41                 //add the parent node copy to the
42                 //current node copy's adjacent list
43                 curr_node_copy.neighbors.add(parent_copy);
44             }
45         }
46     }
47     return g_copy;
48 }

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:
Return 0 if there is no such transformation sequence.

Solution: each word in the dictionary, as well as the start and the end word can be seen as nodes of a graph. There is an edge between two words, if their difference is just one letter. Therefore, the question becomes to construct a graph first, then you can find whether there is a path between the start and end nodes. See the following illustration. Either a BFS or DFS traversal will work.

"hit" --- "hot"-------"dot"
             |             |
           "lot"       "dog"
              \          /   |
              "log" -----"cog"

Java语言: WordLadder

01 public int ladderLength(String start, String end, HashSet<String> dict) {
02     LinkedList<String> queue=new LinkedList<String>();
03     LinkedList<Integer> steps=new LinkedList<Integer>();
04     HashSet<String> visited=new HashSet<String>();
05     queue.add(start);
06     steps.add(1);
07     //This hashtable is used to find neighbors of a given node
08     Hashtable<String, ArrayList<String>> neighborTable=new Hashtable<String, ArrayList<String>>();
09   
10     neighborTable.put(start, new ArrayList<String>());
11     for(String s: dict)
12     {
13         neighborTable.put(s, new ArrayList<String>());
14     }
15     neighborTable.put(end, new ArrayList<String>());
16     //Construct the graph
17     generateGraph(start,end,dict,neighborTable);      
18     while(queue.size()!=0)
19     {
20         String top=queue.remove();
21         int length=steps.remove();
22         ArrayList<String> neighbors=findNeighbors(top,neighborTable);
23         if(neighbors.size()!=0)
24         {
25             for(String s:neighbors)
26             {
27                 if(!visited.contains(s))
28                 {
29                     if(s.equals(end))
30                     {
31                         return length+1;
32                     }
33                     queue.add(s);    
34                     steps.add(length+1);
35                 }
36             }
37             length++;
38         }
39     }
40     return 0;
41 }
42 
43 public void generateGraph(String start, String end, HashSet<String> dict, Hashtable<String, ArrayList<String>> neighborTable)
44 {
45     for(String u:neighborTable.keySet())
46     {
47         ArrayList<String> adj_u=neighborTable.get(u);
48         for(String v:neighborTable.keySet() )
49         {
50             ArrayList<String> adj_v=neighborTable.get(v);
51             if(getDiff(u,v)==1)
52             {
53                 if(!adj_u.contains(v))
54                 {
55                     adj_u.add(v);
56                 }
57                 if(!adj_v.contains(u))
58                 {
59                     adj_v.add(u);
60                 }
61             }
62             neighborTable.put(v, adj_v);              
63         }
64         neighborTable.put(u,adj_u);
65     }
66 }
67 
68 public ArrayList<String> findNeighbors(String word, Hashtable<String,ArrayList<String>>neighborTable)
69 {
70     return neighborTable.get(word);
71 }
72 
73 public int getDiff(String word1, String word2)
74 {
75     if(word1.equals(word2))
76         return 0;
77     int diff=0;      
78     for(int i=0;i<word1.length();i++)
79     {
80         if(word1.charAt(i)!=word2.charAt(i))
81         {
82             diff++;
83         }
84     }
85     return diff;
86 }