# [NineChap 6] Graph and Search

## Graph

For graph, there are only 2 high-frequency questions, which is ‘clone graph’ and ‘topology sorting’.

### Question list

1. Clone Graph - difficult

2. Topology Sorting

## Search

Search have either DFS or BFS.

First, we will cover permutations and combinations using DFS. In this section we solve the famous N-queens question.

Then, there’s a few BFS questions. Graph traversal is BFS, and Word ladder is also a classic BFS question.

### Question list

1. Subsets

2. Subsets II

difficult

3. Permutations

4. Permutations II - difficult

5. N-Queens

how to use hashmap (and some space) to make it faster? 3 hashmaps to store the row, the (x,y) diff and sum. This will make isValid() method O(1).

6. N-Queens II

7. Next Permutation

8. Previous Permutation

9. Palindrome Partitioning

10. Palindrome Partitioning II

11. Combination Sum

12. Combination Sum II

## Code

### Graph

Clone Graph

``````public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
HashMap<UndirectedGraphNode, UndirectedGraphNode> map =
new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
map.put(node, new UndirectedGraphNode(node.label));
while (!queue.isEmpty()) {
UndirectedGraphNode cur = queue.remove();
UndirectedGraphNode copy = map.get(cur);
// here the 'copy' must exist. why? because all neighbors
// has been added to the map when they're pushed to queue.
// so 'cur' must have a corresponding copy in the hashmap.
for (UndirectedGraphNode neib: cur.neighbors) {
if (!map.containsKey(neib)) {
map.put(neib, new UndirectedGraphNode(neib.label));
}
}
}
return map.get(node);
}
``````

Topology Sorting

A new post is written for it.

### Search

Subsets

``````public List<List<Integer>> subsets(int[] num) {
if (num == null || num.length == 0) {
return ans;
}
Arrays.sort(num);
return ans;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int[] num, int pos) {
for (int i = pos; i < num.length; i++) {
helper(ans, path, num, i + 1);
path.remove(path.size() - 1);
}
}
``````

Subsets II

``````public List<List<Integer>> subsetsWithDup(int[] num) {
if (num == null || num.length == 0) {
return ans;
}
Arrays.sort(num);
return ans;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int[] num, int pos) {
for (int i = pos; i < num.length; i++) {
if (i > pos && num[i - 1] == num[i]) {
continue;
}
helper(ans, path, num, i + 1);
path.remove(path.size() - 1);
}
}
``````

Permutations

``````public List<List<Integer>> permute(int[] num) {
if (num == null || num.length == 0) {
return ans;
}
return ans;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int[] num){
if (path.size() == num.length) {
}
for (int i = 0; i < num.length; i++) {
if (path.contains(num[i])) {
continue;
}
helper(ans, path, num);
path.remove(path.size() - 1);
}
}
``````

Permutations II

``````public List<List<Integer>> permuteUnique(int[] num) {
if (num == null || num.length == 0) {
return ans;
}
Arrays.sort(num);
helper(ans, new LinkedList<Integer>(), num, new int[num.length]);
return ans;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int[] num, int[] visited){
if (path.size() == num.length) {
return;
}
for (int i = 0; i < num.length; i++) {
if (visited[i] == 1) {
continue;
}
if (i > 0 && visited[i - 1] == 1 && visited[i] == 0 && num[i - 1] == num[i]) {
// if current number is same as previous, then don't visit current
continue;
}
visited[i] = 1;

helper(ans, path, num, visited);

path.remove(path.size() - 1);
visited[i] = 0;
}
}
``````

N-Queens

``````public List<String[]> solveNQueens(int n) {
if (n <= 0) {
return ans;
}
helper(ans, new int[n], n, 0);
return ans;
}

private void helper(List<String[]> ans, int[] path, int n, int pos) {
if (pos >= n) {
return;
}
for (int i = 0; i < n; i++) {
path[pos] = i;
if (!isValid(path, pos)) {
continue;
}
helper(ans, path, n, pos + 1);
}
}

private String[] convert(int[] path, int n) {
String[] ans = new String[n];
for (int j = 0; j < n; j++) {
ans[j] = "";
for (int i = 0; i < n; i++) {
ans[j] += (j == path[i]) ? 'Q' : '.';
}
}
return ans;
}

private boolean isValid(int[] path, int pos) {
for (int i = 0; i < pos; i++) {
// check path[i] and path[pos]
if (path[i] == path[pos]) {
return false;
}
if (path[i] - path[pos] == pos - i) {
return false;
}
if (path[pos] - path[i] == pos - i) {
return false;
}
}
return true;
}
``````

N-Queens II

``````int total;

public int totalNQueens(int n) {
if (n <= 0) {
return 0;
}
helper(new int[n], n, 0);
}

private void helper(int[] path, int n, int pos) {
if (pos >= n) {
total++;
return;
}
for (int i = 0; i < n; i++) {
path[pos] = i;
if (!isValid(path, pos)) {
continue;
}
helper(path, n, pos + 1);
}
}

private boolean isValid(int[] path, int pos) {
for (int i = 0; i < pos; i++) {
// check path[i] and path[pos]
if (path[i] == path[pos]) {
return false;
}
if (path[i] - path[pos] == pos - i) {
return false;
}
if (path[pos] - path[i] == pos - i) {
return false;
}
}
return true;
}
``````

Next Permutation

``````public void nextPermutation(int[] num) {
if (num == null || num.length <= 1) {
return;
}
int len = num.length;
int p = len - 2;
while (p >= 0 && num[p] >= num[p + 1]) {
p--;
}
if (p < 0) {
Arrays.sort(num);
} else {
int k = len - 1;
while (k >= 0 && num[k] <= num[p]) {
k--;
}
swap(num, p, k);
reverse(num, p + 1, len - 1);
}
}

private void swap(int[] num, int p, int k) {
num[p] = num[p] + num[k];
num[k] = num[p] - num[k];
num[p] = num[p] - num[k];
}

private void reverse(int[] num, int s, int d) {
while (s < d) {
swap(num, s++, d--);
}
}
``````

Previous Permutation

Plz look at the new post.

Palindrome Partitioning

``````public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> ans = new ArrayList<ArrayList<String>>();
if (s == null || s.length() == 0) {
return ans;
}
boolean[][] map = palinMap(s);
helper(ans, new ArrayList<String>(), s, map, 0);
return ans;
}

private void helper(ArrayList<ArrayList<String>> ans, ArrayList<String> path, String s, boolean[][] map, int pos) {
int len = s.length();
if (pos == len) {
return;
}
for (int i = pos; i < len; i++) {
if (!map[pos][i]) {
continue;
}
helper(ans, path, s, map, i + 1);
path.remove(path.size() - 1);
}
}

private boolean[][] palinMap(String s) {
int len = s.length();
boolean[][] map = new boolean[len][len];
for (int i = len - 1; i >= 0; i--) {
for (int j = 0; j < len; j++) {
if (i > j) {
continue;
} else if (i == j) {
map[i][j] = true;
} else if (j - i == 1) {
map[i][j] = s.charAt(i) == s.charAt(j);
} else {
map[i][j] = map[i + 1][j - 1] &
s.charAt(i) == s.charAt(j);
}
}
}
return map;
}
``````

Palindrome Partitioning II

This is DP, not Graph & Search.

Combination Sum

``````public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
if (candidates == null || candidates.length == 0) {
return ans;
}
Arrays.sort(candidates);
helper(ans, new ArrayList<Integer>(), candidates, target, 0);
return ans;
}

private void helper(ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> path,
int[] candidates, int target, int pos) {
if (target == 0) {
return;
} else if (target < 0) {
return;
}
for (int i = pos; i < candidates.length; i++) {
if (target < candidates[i]) {
continue;
}
helper(ans, path, candidates, target - candidates[i], i);
path.remove(path.size() - 1);
}
}
``````

Combination Sum II

``````public ArrayList<ArrayList<Integer>> combinationSum2(int[] candidates, int target) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
if (candidates == null || candidates.length == 0) {
return ans;
}
Arrays.sort(candidates);
helper(ans, new ArrayList<Integer>(), candidates, target, 0);
return ans;
}

private void helper(ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> path,
int[] candidates, int target, int pos) {
if (target == 0) {
return;
} else if (target < 0) {
return;
}
for (int i = pos; i < candidates.length; i++) {
if (target < candidates[i]) {
continue;
}
if (i > pos && candidates[i - 1] == candidates[i]) {
continue;
}
helper(ans, path, candidates, target - candidates[i], i + 1);
path.remove(path.size() - 1);
}
}
``````

Note that this is a BFS question, not DFS. I made it wrong and it took me a long time.

``````public int ladderLength(String start, String end, Set<String> dict) {
int length = 1;

while (!queue.isEmpty()) {
int currentSize = queue.size();
for (int k = 0; k < currentSize; k++) {
String word = queue.remove();
// insert all adjacent strings of word
if (word.equals(end)) {
return length;
}
for (int i = 0; i < word.length(); i++) {
char[] letters = word.toCharArray();
char originalLetter = letters[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == originalLetter) continue;
letters[i] = c;
String newLetters = String.valueOf(letters);
if (dict.contains(newLetters)) {
dict.remove(newLetters);
}
}
letters[i] = originalLetter;
}
}
length++;
}
return 0;
}
``````

unsolvable

``````public List<String> restoreIpAddresses(String s) {
List<String> ans = new ArrayList<String>();
if (s == null || s.length() == 0) {
return ans;
}
helper(ans, new ArrayList<String>(), s, 0);
return ans;
}

private void helper(List<String> ans, List<String> path, String s, int pos) {
if (path.size() == 4) {
if (pos == s.length()) {
}
return;
}
for (int i = pos + 1; i <= s.length() && i <= pos + 3; i++) {
String nextNum = s.substring(pos, i);
if (!isValid(nextNum)) {
continue;
}
helper(ans, path, s, i);
path.remove(path.size() - 1);
}
}

private boolean isValid(String str) {
if (str.length() == 1) {
return true;
} else if (str.charAt(0) == '0') {
return false;
} else {
int num = Integer.parseInt(str);
return 0 <= num && num <= 255;
}
}

private String convert(List<String> path) {
String str = "";
for (String s: path) {
str += "." + s;
}
return str.substring(1);
}
``````

Combinations

skip

Letter Combinations of a Phone Number

skip

Permutation Sequence

``````public String getPermutation(int n, int k) {
List<Integer> list = new ArrayList<Integer>();
int fact = 1;
for (int i = 1; i <= n; i++) {
fact *= i;
}
String ans = "";
for (int i = n; i > 0; i--) {
fact = fact / i;
int rank = (k - 1) / fact;
k = (k - 1) % fact + 1;

int curNum = list.remove(rank);
ans += String.valueOf(curNum);
}
return ans;
}
``````

## Conclusion

#### DFS (O(2n), O(n!))

1. Find all possible solutions
2. Permutations / Subsets

#### BFS (O(m), O(n))

1. Graph traversal
2. Find shortest path in a simple graph

Two most canonical BFS questions:

1. Graph traversal and toposort