图上的DFS

• isVisited
• for(row){ for(column){ helper()}}

构建图

694. Number of Distinct Islands

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

Example 1:
11000
11000
00011
00011
Given the above grid map, return 1.
Example 2:
11011
10000
00001
11011
Given the above grid map, return 3

有什么方法表示一个路径的形状。注意要使用backtracking的思路，加上back

class Solution {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, 1, -1, 0};
    public int numDistinctIslands(int[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        Set<String> set = new HashSet<>();
        int islands = 0;
        for(int i = 0;i < grid.length;i++) {
            for(int j = 0;j < grid[i].length;j++) {
                if(grid[i][j] == 1) {
                    StringBuilder temp = new StringBuilder();
                    temp.append('o');
                    explore(grid,i,j, temp);
                    if (!set.contains(temp.toString())) {
                        set.add(temp.toString());
                        islands++;
                    }
                }
            }
        }
        return islands;
    }
    public static void explore(int[][] grid, int i, int j, StringBuilder temp) {
        grid[i][j] = 0;
        for(int d = 0;d < dx.length; d++) {
            if(i+dy[d]<grid.length && i+dy[d]>=0 && j+dx[d]<grid[0].length && j+dx[d]>=0 && grid[i+dy[d]][j+dx[d]]==1) {
                temp.append(String.valueOf(d));
                explore(grid,i + dy[d], j + dx[d], temp);
                temp.append("b");
            }
        }
    }
}

399. Evaluate Division

构建weighted and directed的图，再用一个hashmap记录weight

742. Closest Leaf in a Binary Tree

Input:
root = [1, 3, 2], k = 1
Diagram of binary tree:
1
/
3 2

Output: 2 (or 3)
给一个数值代表一个node，找出离这个node的最近的叶子节点

首先要找到该节点，再找到距离叶子节点的最短路径。把树转换成一个无向图来做，用dfs建图找点，用BFS找最短路径。
start要声明为全局变量才行
Explanation: Either 2 or 3 is the nearest leaf node to the target of 1.

class Solution {
    TreeNode start = null;
    public int findClosestLeaf(TreeNode root, int k) {
        // key is node, list of its neighbours (parent, left, right children)
        Map<TreeNode, List<TreeNode>> map = new HashMap<>();
        // TreeNode start = null;
        // undirected graph
        helper(map, root, null, k);
        // bfs find shortest path to any leaf node
        Queue<TreeNode> queue = new LinkedList<>();
        Set<TreeNode> visited = new HashSet<>();
        if (start == null) return -2;
        queue.offer(start); 
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll(); 
            // is a leaf node 
            if (cur.right == null && cur.left == null) {
                return cur.val;
            }
            // visited
            visited.add(cur);
            
            for (TreeNode n : map.get(cur)) {
                if (!visited.contains(n)) {
                    queue.add(n);
                }
            }            
        }
        return -1;
    }
    // find k and construct the undirected map 
    public void helper(Map<TreeNode, List<TreeNode>> map, TreeNode root, TreeNode parent, int k) {
        if (root == null) return;
        if (root.val == k) {
            start = root;
        }
        if (parent != null) {
            if (!map.containsKey(parent)) {
                map.put(parent, new ArrayList<>());
            }
            if (!map.containsKey(root)) {
                map.put(root, new ArrayList<>());
            }
            map.get(parent).add(root);
            map.get(root).add(parent);
        }
        helper(map, root.left, root, k);
        helper(map, root.right, root, k);
    }
}

737. Sentence Similarity II

Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.

For example, words1 = ["great", "acting", "skills"] and words2 = ["fine", "drama", "talent"] are similar, if the similar word pairs are pairs = [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]].

Note that the similarity relation is transitive. For example, if "great" and "good" are similar, and "fine" and "good" are similar, then "great" and "fine" are similar.

Similarity is also symmetric. For example, "great" and "fine" being similar is the same as "fine" and "great" being similar.

Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.

Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].

Pair是可以传递的，想到构建图，搜索图，优化的话需要预处理，给每一个连通分量一个ID
1 如何建图 2 区别有向图和无向图 3 情况考虑全面，如果单词相等跳过，如果单词不再pair里，直接返回false

    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
        if (words1.length != words2.length) {
            return false;
        }
        // construct a map by pairs using dfs
        // key word, value the word's neighbours, is an undirected graph
        Map<String, Set<String>> map = new HashMap<>();
        for (String[] pair : pairs) {
            if (map.containsKey(pair[0])) {
                map.get(pair[0]).add(pair[1]);
            } else {
                Set<String> set = new HashSet<>();
                set.add(pair[1]);
                map.put(pair[0], set);
            }
            if (map.containsKey(pair[1])) {
                map.get(pair[1]).add(pair[0]);
            } else {
                Set<String> set = new HashSet<>();
                set.add(pair[0]);
                map.put(pair[1], set);
            }
        }
        for (int i = 0; i < words1.length; i++) {
            // case 1
            if (words1[i].equals(words2[i])) {
                continue;
            }
            if (!helper(words1[i], words2[i], map, new HashSet<>())) {
                return false;
            }
        }
        return true;
    }
    public boolean helper(String source, String target, Map<String, Set<String>> map, Set<String> visited) {
        if (!map.containsKey(source)) {
            return false;
        }
        if (map.get(source).contains(target)) {
            return true;
        }
        Set<String> temp = map.get(source);
        visited.add(source);
        for (String str : temp) {
            if(!visited.contains(str) && helper(str, target, map, visited)) {
                return true;
            }
        }
        return false;
    }

212. Word Search II

给一个char的矩阵和单词list，找出list中在矩阵中的单词
Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must 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 in a word.

For example,
Given words = ["oath","pea","eat","rain"] and board =

[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
Return ["eat","oath"].

注意isVisited。先temp+board[i][j]就不用考虑trie里是否包含空字符串的情况了。字符串不用deep copy

public class Solution {
    Set<String> res = new HashSet<>();
    public List<String> findWords(char[][] board, String[] words) {
        // construct a trie
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                helper(i, j, trie, "", board);
            }
        }
        return new ArrayList<String>(res);
    }
    
    public void helper(int i, int j, Trie trie, String temp, char[][] board) {
        // out of bound
        if (i < 0 || i > board.length -1 || j < 0 || j > board[0].length - 1) {
            return;
        }
        // if visited
        if (board[i][j] == '#') {
            return;
        }
        temp = temp + board[i][j];
        if (!trie.startWith(temp)) {
            return;
        }
        // if in trie, add to res
        if (trie.search(temp)) {
            res.add(temp);
        }
        int[] directionX = {0, 0, 1, -1};
        int[] directionY = {1, -1, 0, 0};
        for (int k = 0; k < 4; k++) {
            char cur = board[i][j];
            board[i][j] = '#';
            helper(i + directionX[k], j + directionY[k], trie, temp, board);
            board[i][j] = cur;
        }
    }
}

286. Walls and Gates

-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room.
For example, given the 2D grid:
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4

DFS BFS都可以做，需要注意的是以门为起点去向下延伸，而不是以房间开始

public void wallsAndGates(int[][] rooms) {
    for (int i = 0; i < rooms.length; i++)
        for (int j = 0; j < rooms[0].length; j++)
            if (rooms[i][j] == 0) dfs(rooms, i, j, 0);
}

private void dfs(int[][] rooms, int i, int j, int d) {
  // 注意rooms[i][j] < d
    if (i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] < d) return;
    rooms[i][j] = d;
    dfs(rooms, i - 1, j, d + 1);
    dfs(rooms, i + 1, j, d + 1);
    dfs(rooms, i, j - 1, d + 1);
    dfs(rooms, i, j + 1, d + 1);
}

200. Number of Islands

给一个二维数组算岛屿的数量，有多少个连着的1

遍历二维数组，发现1之后调用helper函数向四周扩展一步，并把该位置的1换成0。
再发现1，再次调用helper
注意越界的情况 可以写一个单独的函数inbound判断

    static int[] dx = {-1,0,0,1};
    static int[] dy = {0,1,-1,0};
    public static int numIslands(char[][] grid) {
        if(grid==null || grid.length==0) return 0;
        int islands = 0;
        for(int i=0;i<grid.length;i++) {
            for(int j=0;j<grid[i].length;j++) {
                if(grid[i][j]=='1') {
                    explore(grid,i,j);
                    islands++;
                }
            }
        }
        return islands;
    }
    public static void explore(char[][] grid, int i, int j) {
        grid[i][j]='0';
        for(int d=0;d<dx.length;d++) {
            if(i+dy[d]<grid.length && i+dy[d]>=0 && j+dx[d]<grid[0].length && j+dx[d]>=0 && grid[i+dy[d]][j+dx[d]]=='1') {
                explore(grid,i+dy[d],j+dx[d]);
            }
        }
    }

DFS + Backtracking + 剪枝

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

注意stringbuilder如何backtrack的

public List<String> generateParenthesis(int n) {
     List<String> res = new ArrayList<>();
     helper(res, new StringBuilder(), 0, 0, n);
     return res;
}

private void helper(List<String> res, StringBuilder sb, int open, int close, int n) {
    if(open == n && close == n) {
        res.add(sb.toString());
        return;
    }
    
    if(open < n) {
        sb.append("(");
        helper(res, sb, open+1, close, n);
        sb.setLength(sb.length()-1);
    } 
    if(close < open) {
        sb.append(")");
        helper(res, sb, open, close+1, n);
        sb.setLength(sb.length()-1);
    }
}

301. Remove Invalid Parentheses

给一个String ()()())，移除最少的invalid括号使string valid

和上一题一样，需要遍历所有可能性，所以用dfs + backtracking，有一个地方可以剪枝就是观察String，保证剩下的最长就需要让删除的少，发现最少删除一个右括号就可以使其valid，所以把最少删除的右括号和左括号的数量作为参数传入DFS中
可以尝试画递归树，题目说删东西不要一味想去remove，也可以是建空白的往里加

class Solution {
   public List<String> removeInvalidParentheses(String s) {
       Set<String> res = new HashSet<>();
       if (s == null || s.length() == 0) {
           return new ArrayList<String>();
       }
       // remove maximum number of right or left, otherwise the dfs will try all the possibilities
       int maxRight = 0, maxLeft = 0;
       for (char c : s.toCharArray()) {
           if (c == '(') {
               maxLeft++;
           } else if (c == ')') {
               if (maxLeft == 0) {
                   maxRight++;;
               } else {
                   maxLeft--;
               }
           } else {
              // ignore 
           }
       }
       helper(s, 0, new StringBuilder(), res, maxLeft, maxRight, 0);
       return new ArrayList<String>(res);
   }
   public void helper(String s, int index, StringBuilder temp, Set<String> res, int maxLeft, int maxRight, int count) {
       // base case
       if (index == s.length()) {
           if (count == 0 && maxLeft == 0 && maxRight == 0) {
               res.add(temp.toString());
           }  
           return;
       }

       if (maxLeft < 0 || maxRight < 0 || count < 0) {
           return;
       }
       char cur = s.charAt(index);
       int len = temp.length();
       if (cur == '(') {
           helper(s, index + 1, temp.append('('), res, maxLeft, maxRight, count + 1); // keep
           helper(s, index + 1, temp, res, maxLeft - 1, maxRight, count); // delete a (
       } else if (cur == ')') {
           helper(s, index + 1, temp.append(')'), res, maxLeft, maxRight, count - 1);
           helper(s, index + 1, temp, res, maxLeft, maxRight - 1, count); // delete a )           
       } else {
           helper(s, index + 1, temp.append(cur), res, maxLeft, maxRight, count);
       }
       // backtracking
       temp.setLength(len);
   }
}

17. Letter Combinations of a Phone Number

手机键盘输入数字，计算出所有组合的可能性

有“所有”出现，想到穷举，dfs
dfs的核心是helper函数的传入参数，传入：当前的组合String temp，结果ArrayList of String，输入字符串处理到第几位的index

Word Search

140. Word Break II

s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

DFS + Memo
注意base case的add（“”）

    public List<String> wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null) {
            return null;
        }
        Map<String, List<String>> map = new HashMap<>();
        Set<String> set = new HashSet<>();
        for (String word : wordDict) {
            set.add(word);
        }
        return helper(s, set, map);
    }
    public List<String> helper(String s, Set<String> set, Map<String, List<String>> map) {
        List<String> res = new ArrayList<>();
        // find
        if (s.length() == 0) {
            // 区分什么都没找到的情况
            res.add("");
            return res;
        }
        if (map.containsKey(s)) return map.get(s);
        // 注意 i <=
        for (int i = 1; i <= s.length(); i++) {
            String sub = s.substring(0, i);
            if (set.contains(sub)) {
                List<String> temp = helper(s.substring(i, s.length()), set, map);
                if (temp.size() > 0) {
                    for (String word : temp) {
                        String s1 = sub + " " + word;
                        res.add(s1.trim());                 
                    }
                }
            }
        }
        map.put(s, res);
        return res;        
    }

425. Word Squares

找所有的square组合
Input:
["abat","baba","atan","atal"]
Output:
[
[ "baba",
"abat",
"baba",
"atan"
],
[ "baba",
"abat",
"baba",
"atal"
]
]

Trie + Backtracking + 剪枝
Trie 有一个不同的是加了一个startwith的list，方便找以指定字符串开头的所有字符串
1 根据temp的size找第几列，一开始没想明白
2 Trie的startWith字段

class Solution {
    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> res = new ArrayList<>();
        if (words == null || words.length == 0) {
            return res;
        }
        Trie trie = new Trie(words);
        List<String> temp = new ArrayList<>();
        for (String word : words) {
            temp.add(word);
            helper(temp, res, trie, word.length());
            temp.remove(0);
        }
        return res;
    }
    
    public void helper(List<String> temp, List<List<String>> res, Trie trie, int len) {
        int size = temp.size();
        if (size == len) {
            res.add(new ArrayList<>(temp));
            return;
        }
        
        StringBuilder prefix = new StringBuilder();
        for (String s : temp) {
            if(size <= s.length() - 1) {
                 prefix.append(s.charAt(size));               
            } else {
                return;
            }
        }
        // backtracking
        List<String> candidates = trie.findByPrefix(prefix.toString());
        
        for (String c : candidates) {
            //if (!temp.contains(c)) {
                temp.add(c);
                helper(temp, res, trie, len);
                temp.remove(temp.size() - 1);               
            //}
        }
    }
}
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isWord = false;
    List<String> startWith = new ArrayList<>();
    public TrieNode() {}
}
class Trie {
    TrieNode root;
    public Trie (String[] words) {
        root = new TrieNode();
        // add into trie
        for (String word : words) {
            insert(word);
        }
    }
    private void insert(String str) {
        TrieNode cur = root;
        for (char c : str.toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                cur.children[c - 'a'] = new TrieNode();
            }
            cur.children[c - 'a'].startWith.add(str);
            cur = cur.children[c - 'a'];
        }
        cur.isWord = true;
    }
    public List<String> findByPrefix(String str) {
        TrieNode cur = root;
        for (char c : str.toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                return list;
            }
            cur = cur.children[c - 'a'];
        }
        return cur.startWith;
    }
}

140. Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

    public List<String> wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null) {
            return null;
        }
        Map<String, List<String>> map = new HashMap<>();
        Set<String> set = new HashSet<>();
        for (String word : wordDict) {
            set.add(word);
        }
        return helper(s, set, map);
    }
    public List<String> helper(String s, Set<String> set, Map<String, List<String>> map) {
        List<String> res = new ArrayList<>();
        // find
        if (s.length() == 0) {
            // 区分什么都没找到的情况
            res.add("");
            return res;
        }
        if (map.containsKey(s)) return map.get(s);
        // 注意 i <=
        for (int i = 1; i <= s.length(); i++) {
            String sub = s.substring(0, i);
            if (set.contains(sub)) {
                List<String> temp = helper(s.substring(i, s.length()), set, map);
                if (temp.size() > 0) {
                    for (String word : temp) {
                        String s1 = sub + " " + word;
                        res.add(s1.trim());                 
                    }
                }
            }
        }
        map.put(s, res);
        return res;        
    }

DFS helper带返回值的情况

There is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, ..., k-1.
You can keep inputting the password, the password will automatically be matched against the last n digits entered.
For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.
Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.
Example 2:
Input: n = 2, k = 2
Output: "00110"
Note: "01100", "10011", "11001" will be accepted too.

不需要遍历出所有的情况，有一种满足条件就退出，不满足再回溯
注意代码里的细节

class Solution {
    public String crackSafe(int n, int k) {
        int total = (int) (Math.pow(k, n));
        Set<String> visited = new HashSet<>();
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < n; i++) {
            res.append('0');
        }
        visited.add(res.toString());
        helper(total, visited, res, n, k);
        
        return res.toString();

    }
    public boolean helper(int total, Set<String> visited, StringBuilder res, int n, int k) {
        if (total == visited.size()) {
            return true;
        }
        // reuse the last n-1 digits
        // stringbuilder substring
        // 从 res拿出最后的 n-1 位 比如res XXXXX 需要一个n=3位的密码，所以从res中取出后两位，再加上新的一位构成新密码
        String prev = res.substring(res.length() - n + 1, res.length());
        // next step 0,1,2,3...
        for (int i = 0; i < k; i++) {
            String cur = prev + i;
            if (!visited.contains(cur)) {
                res.append(i); 
                visited.add(cur);
                if(helper(total, visited, res, n, k)) {
                    return true;
                }
                // backtracking
                visited.remove(cur);
                // stringbuilder delete last 
                res.delete(res.length() - 1, res.length());
            }
        }
        return false;
    }
}