trie, backtracking

trie

Tree structure. Each node contains:

  • vector<TrieNode*> children
  • bool isWord

API:

  • insert: same as building the trie: traverse each word from given, take the char, create a TrieNode if null and move cur like in a LinkedList, iterate through. When it's done, flag it as a word.
  • search
  • startsWith
class Trie {

    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); ++i) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        node.isWord = true;
    }
    
    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); ++i) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) return false;
            node = node.children[c - 'a'];
        }
        return node.isWord;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); ++i) {
            char c = prefix.charAt(i);
            if (node.children[c - 'a'] == null) return false;
            node = node.children[c - 'a'];
        }
        return true;
    }
}

class TrieNode {
    public TrieNode[] children = new TrieNode[26];
    public boolean isWord;
    public TrieNode() {}
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Notice that

if (node.children[c - 'a'] == null) return false;
node = node.children[c - 'a'];

"self-indexing" inside a loop until hits an end: similar to union all nodes of the same root on one branch.

backtracking + trie: use the trie from wordSet for terminal condition. In this case, sets: wordSet or firstChar would not work as would trie.

word search ii

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word;
}

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList();
        int m = board.length, n = board[0].length;
        
        TrieNode root = buildTrie(words);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                dfs(board, i, j, root, res);
            }
        }
        return res;
    }
    
    private void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
        char c = board[i][j];
        if (c == '#' || p.children[c - 'a'] == null) return;
        p = p.children[c - 'a'];
        if (p.word != null) {
            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.children[i] == null) p.children[i] = new TrieNode();
                p = p.children[i];
            }
            p.word = w;
        }
        return root;
    }
}

Or if trie is not involved, plain backtracking:

word search

public boolean exist(char[][] board, String word) {
        if (board.length == 0 || board[0].length == 0) return false;
        int m = board.length, n = board[0].length;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (search(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean search(char[][] board, int i, int j, String word, int index) {
        if (index == word.length()) return true;
        int m = board.length, n = board[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] != word.charAt(index)) 
            return false;
        char c = board[i][j];
        board[i][j] = '#';
        
        boolean res = false;
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = i, y = j;
        for (int k = 0; k < 4; ++k) {
            res = res || search(board, x+dirs[k][0], y+dirs[k][1], word, index+1);
        }
        
        board[i][j] = c;
        return res;
    }

plain backtracking

illustrations

Superb explanation. Think one possible solution out of all, as base case; then add constraints, iterate through all possible choices one time, backtrack, and retreat back to previous state.

17

class Solution {
    Map<Character, String> map = new HashMap();
    
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList();
        if (digits.length() == 0) return res;
        
        map.put('2', "abc"); map.put('3', "def"); map.put('4', "ghi"); map.put('5', "jkl"); 
        map.put('6', "mno"); map.put('7', "pqrs"); map.put('8', "tuv"); map.put('9', "wxyz");
        
        StringBuilder sb = new StringBuilder();
        backtrack(res, sb, digits);
        return res;
    }
    
    private void backtrack(List<String> res, StringBuilder sb, String digits) {
        if (sb.length() == digits.length()) {
            res.add(sb.toString());
            return;
        }
        
        String s = map.get(digits.charAt(sb.length()));
        
        for (char c : s.toCharArray()) {
            sb.append(c);
            backtrack(res, sb, digits);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

39 unique and can be used multiple times; iteration should not go back, starting from cur and only goes after.

class Solution {
    
    public List<List<Integer>> combinationSum(int[] c, int target) {
        List<List<Integer>> res = new ArrayList();
        if (c.length == 0) return res;
        
        List<Integer> tmp = new ArrayList();
        backtrack(res, tmp, c, target, 0);
        return res;
    }
    
    private void backtrack(List<List<Integer>> res, List<Integer> tmp, int[] c, int target, int start) {
        if (target < 0) return;
        else if (target == 0) {
            res.add(new ArrayList(tmp));
            return;
        }
        
        for (int i = start; i < c.length; ++i) {
            tmp.add(c[i]);
            backtrack(res, tmp, c, target - c[i], i);
            tmp.remove(tmp.size() - 1);
        }
    }
}

Compare 39 with 40, pattern are the same, only constraints differ.
40: same val number seen as same answer, though different num. When hit, slide to right until different number.

class Solution {
    public List<List<Integer>> combinationSum2(int[] c, int target) {
        List<List<Integer>> res = new ArrayList();
        if (c.length == 0) return res;
        Arrays.sort(c);
        List<Integer> tmp = new ArrayList();
        backtrack(res, tmp, c, target, 0);
        return res;
    }
    
    private void backtrack(List<List<Integer>> res, List<Integer> tmp, int[] c, int target, int start) {
        if (target < 0) return;
        if (target == 0) {
            res.add(new ArrayList(tmp));
            return;
        }
        
        for (int i = start; i < c.length; ++i) {
            if (i > start && c[i] == c[i-1]) continue;
            tmp.add(c[i]);
            backtrack(res, tmp, c, target - c[i], i+1);
            tmp.remove(tmp.size() - 1);
        }
    }
}

Notice it's if (i > start && c[i] == c[i-1]) continue; instead of if (i > 0 && c[i] == c[i-1]) continue;: when i=start, this number should be examined, not just skipped: evade when curVal == prevVal and just skipped, though different number

  1. no sorting; each time start from 0. The way to evade duplicates is if (tmp.contains(n[i])) continue; since each time starting from 0. Notice the 4th param start can exist, or not, in the backtrack signature cuz it's going to backtrack from i+1 next time.
class Solution {
    public List<List<Integer>> permute(int[] n) {
        List<List<Integer>> res = new ArrayList();
        if (n.length == 0) return res;
        List<Integer> tmp = new ArrayList();
        backtrack(res, tmp, n, 0);
        return res;
    }
    
    private void backtrack(List<List<Integer>> res, List<Integer> tmp, int[] n, int start) {
        if (tmp.size() == n.length) {
            res.add(new ArrayList(tmp));
            return;
        }
        for (int i = 0; i < n.length; ++i) {
            if (tmp.contains(n[i])) continue;
            tmp.add(n[i]);
            backtrack(res, tmp, n, i+1);
            tmp.remove(tmp.size() - 1);
        }
    }
}
  1. Pruning: if (used[i] || i > 0 && nums[i-1] == nums[i] && used[i-1] == false) continue;; sort and use used[i] to record if this number was used before; Retreat: undo used[i] as well
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> tmp = new ArrayList();
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        backtrack(res, tmp, nums, used);
        return res;
    }
    
    private void backtrack(List<List<Integer>> res, List<Integer> tmp, int[] nums, boolean[] used) {
        if (tmp.size() == nums.length) {
            res.add(new ArrayList(tmp));
            return;
        }
        
        for (int i = 0;  i< nums.length; ++i) {
            if (used[i] || i > 0 && nums[i-1] == nums[i] && used[i-1] == false) continue;
            used[i] = true;
            tmp.add(nums[i]);
            
            backtrack(res, tmp, nums, used);
            
            used[i] = false;
            tmp.remove(tmp.size() - 1);
        }
    }
}

77

public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> tmp = new ArrayList();
        backtrack(res, tmp, n, k, 1);
        return res;
    }
    
    private void backtrack(List<List<Integer>> res, List<Integer> tmp, int n, int k, int start) {
        if (k == 0) {
            res.add(new ArrayList(tmp));
            return;
        }
        for (int i = start; i <= n-k+1; ++i) {
            tmp.add(i);
            backtrack(res, tmp, n, k-1, i+1);
            tmp.remove(tmp.size() - 1);
        }
    }

78

public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> tmp = new ArrayList();
        backtrack(res, tmp, nums, 0);
        return res;
    }
    
    private void backtrack(List<List<Integer>> res, List<Integer> tmp, int[] nums, int start) {
        res.add(new ArrayList(tmp));
        for (int i = start; i < nums.length; ++i) {
            tmp.add(nums[i]);
            backtrack(res, tmp, nums, i+1);
            tmp.remove(tmp.size() - 1);
        }
    }
  1. N-queens
class Solution {
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                board[i][j] = '.';
            }
        }
        List<List<String>> res = new ArrayList();
        backtrack(board, res, 0);
        return res;
    }
    
    private void backtrack(char[][] board, List<List<String>> res, int row) {
        int n = board.length;
        if (row == n) {
            res.add(build(board));
            return;
        }
        
        for (int i = 0; i < n; ++i) {
            if (isValid(board, row, i)) {
                board[row][i] = 'Q';
                backtrack(board, res, row + 1);
                board[row][i] = '.';
            }
        }
    }
    
    private boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < row; ++i) {
            if (board[i][col] == 'Q') 
                return false;
        }
        for (int i = row -1, j = col - 1; i >=0 && j >= 0; --i, --j) {
            if (board[i][j] == 'Q') 
                return false;
        }
        for (int i = row -1, j = col + 1; i >=0 && j < board.length; --i, ++j) {
            if (board[i][j] == 'Q')
                return false;
        }
        
        return true;
    }
    
    private List<String> build(char[][] board) {
        List<String> res = new ArrayList();
        for (int i = 0; i < board.length; ++i) {
            String s = new String(board[i]);
            res.add(s);
        }
        return res;
    }
}
  1. Sudoku Solver
class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) return;
        solve(board);
    }
    
    private boolean solve(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; ++c) {
                        if (isValid(board, c, i, j)) {
                            board[i][j] = c;
                            if (solve(board)) 
                                return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private boolean isValid(char[][] board, char c, int row, int col) {
        int cubeRowStart = 3 * (row / 3);
        int cubeColStart = 3 * (col / 3);
        for (int i = 0; i < 9; ++i) {
            if (board[row][i] == c) return false;
            if (board[i][col] == c) return false;
            if (board[cubeRowStart + i / 3][cubeColStart + i % 3] == c) return false;
        }
        return true;
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,311评论 6赞 481
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,339评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 152,671评论 0赞 342
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,252评论 1赞 279
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,253评论 5赞 371
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,031评论 1赞 285
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,340评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,973评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,466评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,937评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,039评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,701评论 4赞 323
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,254评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,259评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,485评论 1赞 262
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,497评论 2赞 354
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,786评论 2赞 345

推荐阅读更多精彩内容