Clone Graph, Populating Next Right Pointers in Each Node, Populating Next Right Pointers in Each Node II, Word Ladder, Word Ladder II

Posted on 2015-09-23   |   In 刷题   |  

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ’s undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

1
2
3
4
5
6
   1
  / \
 /   \
0 --- 2
     / \
     \_/

BFS Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
       // use a map to save cloned nodes
       if(node==null) return null;
	HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
       LinkedList<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
       q.offer(node);
       // clone the root
       map.put(node, new UndirectedGraphNode(node.label));
       while(!q.isEmpty()){
           UndirectedGraphNode cur = q.poll();
           for (UndirectedGraphNode neighbor : cur.neighbors) {
               if(!map.containsKey(neighbor)){
                   map.put(neighbor, new UndirectedGraphNode(neighbor.label));
                   q.offer(neighbor);
               }
               map.get(cur).neighbors.add(map.get(neighbor));
           }
       }
       return map.get(node);
   }

Populating Next Right Pointers in Each Node

Given a binary tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
         1
       /  \
      2    3
     / \  / \
    4  5  6  7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Two pointer Solution

  • cur-keep the start of next level ; last-keep iterating the last level
  • if last has left child, then child’s next=last.right
  • if last has no left child, then reached leaf
  • if last has next, then right child’s next=last.next.left
  • if last has no next, we reached end of that layer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void connect(TreeLinkNode root) {
        if(root == null)
            return;
        TreeLinkNode last = root; //previous level pointer
        TreeLinkNode cur = null;//current level head
        while(last!=null){
            if(cur==null){
                cur=last.left;//cur level head-leftmost subtree
            }
            if(last.left!=null){//如果一个子节点是根节点的左子树，那么它的next就是该根节点的右子树
                last.left.next=last.right;
            }
            else{
                break;
            }
            if(last.next!=null){//如果一个子节点是根节点的右子树，那么它的next就是该根节点next节点的左子树
                last.right.next=last.next.left;
                last=last.next;
            }
            else{
                last=cur;
                cur=null;
            }
        }
    }

Populating Next Right Pointers in Each Node II

Follow up for problem “Populating Next Right Pointers in Each Node”.
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
For example,

1
2
3
4
5
6
7
8
9
10
11
12
Given the following binary tree,
         1
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Four Pointer Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public void connect(TreeLinkNode root) {
    if(root == null)
        return;
    TreeLinkNode lastHead = root; //previous level head
    TreeLinkNode pre = null;//current level pointer
    TreeLinkNode curHead = null;//current level head
    while(lastHead!=null)
    {
        TreeLinkNode lastCur = lastHead;//previous level pointer
        while(lastCur != null)
        {
            if(lastCur.left!=null)
            {
                if(curHead == null)
                {
                    curHead = lastCur.left;
                    pre = curHead;
                }
                else
                {
                    pre.next = lastCur.left;
                    pre = pre.next;
                }
            }
            if(lastCur.right!=null)
            {
                if(curHead == null)
                {
                    curHead = lastCur.right;
                    pre = curHead;
                }
                else
                {
                    pre.next = lastCur.right;
                    pre = pre.next;
                }
            }                
            lastCur = lastCur.next;
        }
        lastHead = curHead;
        curHead = null;
    }
}

Word Ladder II

Word Ladder II My Submissions Question Solution
Total Accepted: 31002 Total Submissions: 234902 Difficulty: Hard
Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,
Given:
beginWord = “hit”
endWord = “cog”
wordList = [“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.

BFS + DFS Solution

  • BFS once to find shortest path, stored all neighbors, and ladder map
  • DFS to output shortest path, start from end, check each time to see if we are on the shortest path (ladder.get(s) == (ladder.get(end)-1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public static List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
        HashMap<String, List<String>> neighbors = new HashMap<String, List<String>>();
        HashMap<String, Integer> ladder = new HashMap<String, Integer>();
        bfs(beginWord, endWord, wordList, neighbors, ladder);
        List<String> path=new ArrayList<String>();
        List<List<String>> res= new ArrayList<List<String>>();
        dfs(neighbors, ladder, path, res, endWord, beginWord);
        return res;
    }
    
    private static void dfs( HashMap<String, List<String>> neighbors, HashMap<String, Integer> ladder, List<String> path, List<List<String>> res, String end, String start){
        path.add(end);
        if(end.equals(start)){
            Collections.reverse(path);
            res.add(new ArrayList<String>(path));
            Collections.reverse(path);
            path.remove(path.size()-1);
            return;
        }
        List<String> parents = neighbors.get(end);
        for(String s : parents){
            if(ladder.get(s) == (ladder.get(end)-1)){
                dfs(neighbors, ladder, path, res, s, start);
            }            
        }
        path.remove(path.size()-1);
    }
    private static void bfs(String begin, String end, Set<String> wordlist, HashMap<String, List<String>> neighbors, HashMap<String, Integer> ladder){
        wordlist.add(begin); wordlist.add(end);
        LinkedList<String> q = new LinkedList<String>();
        q.offer(begin);
        ladder.put(begin, 0);
        for(String s : wordlist){//create adjacency list for each word
            neighbors.put(s, new ArrayList<String>());
        }
        while(!q.isEmpty()){
            String cur=q.poll();
            ArrayList<String> nextlayer = findnext(cur, wordlist);
            for(String next : nextlayer){
                neighbors.get(cur).add(next);//add to adjacency list
                if(!ladder.containsKey(next)){//update shortest path count 
                    ladder.put(next, ladder.get(cur) + 1);
                    q.offer(next);
                }
                
            }
        }
    }
    private static ArrayList<String> findnext(String cur, Set<String> wordlist){
        ArrayList<String> nextlayer = new ArrayList<String>();
        for(int i=0;i<cur.length();i++){
            for(char c='a'; c<='z'; c++){
                if(!(cur.charAt(i)==c)){
                    String next=cur.substring(0,i) + c + cur.substring(i+1);
                    if(wordlist.contains(next)) nextlayer.add(next);
                }
            }
        }
        return nextlayer;
    }

Two End BFS Solution

  • BFS from two end finds shortest path fast, stored in a map
  • DFS to output shortest paths
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
public static List<List<String>> findLadders(String start, String end, Set<String> dict) {
	// hash set for both ends
	Set<String> set1 = new HashSet<String>();
	Set<String> set2 = new HashSet<String>();
	// initial words in both ends
	set1.add(start);
	set2.add(end);
	// we use a map to help construct the final result
	HashMap<String, List<String>> map = new HashMap<String, List<String>>();
	// build the map
	helper(dict, set1, set2, map, false);
	List<List<String>> res = new ArrayList<List<String>>();
	List<String> sol = new ArrayList<String>(Arrays.asList(start));
	// recursively build the final result
	generateList(start, end, map, sol, res);
	return res;
}
static boolean helper(Set<String> dict, Set<String> set1, Set<String> set2, HashMap<String, List<String>> map, boolean flip) {
	if (set1.isEmpty()) {
		return false;
	}
	if (set1.size() > set2.size()) {
		return helper(dict, set2, set1, map, !flip);
	}
	// remove words on current both ends from the dict
	dict.removeAll(set1);
	dict.removeAll(set2);
	// as we only need the shortest paths
	// we use a boolean value help early termination
	boolean done = false;
	// set for the next level
	Set<String> set = new HashSet<String>();
	// for each string in end 1
	for (String str : set1) {
		for (int i = 0; i < str.length(); i++) {
			// change one character for every position
			for (char ch = 'a'; ch <= 'z'; ch++) {
				char[] chars = str.toCharArray();
				chars[i] = ch;
				String word = new String(chars);
				// make sure we construct the tree in the correct direction
				String key = flip ? word : str;
				String val = flip ? str : word;
				List<String> list = map.containsKey(key) ? map.get(key) : new ArrayList<String>();
				if (set2.contains(word)) {
					done = true;
					list.add(val);
					map.put(key, list);
				} 
				if (!done && dict.contains(word)) {
					set.add(word);
					list.add(val);
					map.put(key, list);
				}
			}
		}
	}
	// early terminate if done is true
	return done || helper(dict, set2, set, map, !flip);
}
static void generateList(String start, String end, HashMap<String, List<String>> map, List<String> sol, List<List<String>> res) {
	if (start.equals(end)) {
		res.add(new ArrayList<String>(sol));
		return;
	}
	// need this check in case the diff between start and end happens to be one
	// e.g "a", "c", {"a", "b", "c"}
	if (!map.containsKey(start)) {
		return;
	}
	for (String word : map.get(start)) {
		sol.add(word);
		generateList(word, end, map, sol, res);
		sol.remove(sol.size() - 1);
	}
}
#Graph #BFS #DFS #Backtracking #LinkedList
Lowest Common Ancestor of a Binary Search Tree, Lowest Common Ancestor of a Binary Tree, Invert Binary Tree, Kth Smallest Element in a BST, Binary Tree Right Side View, Count Complete Tree Nodes
Path Sum, Path Sum II, Binary Tree Maximum Path Sum, Binary Tree Paths, Sum Root to Leaf Numbers