矩阵中的DFS

Description

212.Word Search II
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"].
Note:You may assume that all inputs are consist of lowercase letters a-z.

216.Combination Sum III
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
Input: k = 3, n = 7
Output:

[[1,2,4]]

Example 2:
Input: k = 3, n = 9
Output:

1	[[1,2,6], [1,3,5], [2,3,4]]

Solution

矩阵中的DFS太过于常见了，DFS套for循环，for循环套DFS，这里就举出一些例子来说明，有固定的写法，很简单，如果可以优化的话，一般需要用DP来代替.

[leetcode 212] Word Search II

这里其实是很简单的一道题，无非就是遍历矩阵中的每个元素，作为字符串的起点，然后使用dfs来找出是否存在匹配给定的单词集中的单词，之所以讲这道题，是因为有一个在leetcode上beats96%的解Java 15ms Easiest Solution (100.00%)
主要是构建了一个TrieNode，然后将单词集按字符组成了一个分叉链表(不同的起点的链表集或者是同一个起点，但是后面分叉的链表)，还是直接看代码吧：

public List<String> findWords(char[][] board, String[] words) {
    List<String> res=new ArrayList<>();
    TrieNode root = buildTrie(words);
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            dfs (board, i, j, root, res);
        }
    }
    return res;
}
public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
    char c = board[i][j];
    if (c == '#' || p.next[c - 'a'] == null) return;
    p = p.next[c - 'a'];
    if (p.word != null) {   // found one
        res.add(p.word);
        p.word = null;     // de-duplicate
    }
    board[i][j] = '#';
    if (i > 0) dfs(board, i - 1, j ,p, res);
    if (j > 0) dfs(board, i, j - 1, p, res);
    if (i < board.length - 1) dfs(board, i + 1, j, p, res);
    if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);
    board[i][j] = c;
}
public TrieNode buildTrie(String[] words){
    TrieNode root=new TrieNode();
    for(String w:words){
        TrieNode p=root;
        for(char c:w.toCharArray()){
            int i=c-'a';
            if(p.next[i]==null)p.next[i]=new TrieNode();
            p=p.next[i];
        }
        p.word=w;
    }
    return root;
}
class TrieNode{
TrieNode[] next=new TrieNode[26];
String word;
}

[leetcode 216] Combination Sum III

从1开始取，可以取1也可以不取1，每次取完后都从list中的最后一个元素加1开始取下一个元素，代码如下（很常规但很经典）：

public static List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>>lists=new ArrayList<>();
    ArrayList<Integer> list=new ArrayList<>();
    dfs(lists,list,0,0,k,n);
    return lists;
}
private static void dfs(List<List<Integer>> lists, ArrayList<Integer> list, int sum, int num,int k, int n) {
    if(sum==n&&num==k)lists.add(new ArrayList<>(list));
    else if(sum<n&&num<k){
        for(int i=list.size()==0?1:list.get(list.size()-1)+1;i<=9;i++){
            list.add(i);
            dfs(lists,list,sum+i,num+1,k,n);
            list.remove(list.size()-1);
        }
    }
}