Trie 系列

208. Implement Trie (Prefix Tree)

Medium

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 104 calls in total will be made to insert, search, and startsWith.

class Trie {
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
    }
    private TrieNode root=null;
    public Trie() {
        root = new TrieNode();
    }
    public void insert(String word) {
        TrieNode curr = root;
        for(char c:word.toCharArray()){
            if(curr.children[c-'a']==null) curr.children[c-'a']=new TrieNode();
            curr = curr.children[c-'a'];
        }
        curr.isWord=true;
    }
    public boolean search(String word) {
        TrieNode curr = root;
        for(char c:word.toCharArray()){
            if(curr.children[c-'a']==null) return false;;
            curr = curr.children[c-'a'];
        }
        return curr.isWord;
    }
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for(char c:prefix.toCharArray()){
            if(curr.children[c-'a']==null) return false;;
            curr = curr.children[c-'a'];
        }
        return true;
    }
}

时间复杂度：O(Len)

211. Design Add and Search Words Data Structure

Medium

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Constraints:

• 1 <= word.length <= 500
• word in addWord consists lower-case English letters.
• word in search consist of  '.' or lower-case English letters.
• At most 50000 calls will be made to addWord and search.

class WordDictionary {
    TrieNode root;
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
    }
    public WordDictionary() {
        root = new TrieNode();
    }
    public void addWord(String word) {
        TrieNode curr = root;
        for(char c:word.toCharArray()){
            if(curr.children[c-'a']==null) curr.children[c-'a'] = new TrieNode();
            curr = curr.children[c-'a'];
        }
        curr.isWord=true;
    }
    public boolean search(String word){
        return search(word,root);
    }
    private boolean search(String word,TrieNode start) {
        if(word.length()==0) return start.isWord;
        TrieNode curr = start;
        for(int i=0;i){
            char c = word.charAt(i);
            if(c=='.'){
                for(int j=0;j<26;j++){
                    if(curr.children[j]!=null && search(word.substring(i+1),curr.children[j])) return true;
                }
                return false;
            }
            if(curr.children[c-'a']==null) return false; 
            curr = curr.children[c-'a'];
        }
        return curr.isWord;
    }
}

时间复杂度：所有字符串长度和为totalLen, 时间复杂度O(totalLen) , 查找单个len长度的字符串时间复杂度 O(len)

212. Word Search II

Hard

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

class Solution {
    private TrieNode root=null;
    public List findWords(char[][] board, String[] words) {
        //trie build
        root = new TrieNode();
        for(String str:words) insert(str);
        int m = board.length,n=board[0].length;
        //set 为了去重
        Set result = new HashSet();
        boolean[][] visited = new boolean[m][n];
        //循环遍历每个元素，dfs进行trie搜索
        for(int i=0;i){
            for(int j=0;j){
                helper(visited,result,i,j,root,"",board);
            }
        }
        return new ArrayList(result);
    }
    private void helper(boolean[][] visited,Set result,int i,int j,TrieNode root,String curr,char[][] board){
        if(i<0||j<0||i>=visited.length||j>=visited[0].length) return;
        if(visited[i][j]) return;
        visited[i][j]=true;
        char c = board[i][j];
        if(root.children[c-'a']!=null){
            if(root.children[c-'a'].isWord) result.add(curr+c);
            helper(visited,result,i-1,j,root.children[c-'a'],curr+c,board);
            helper(visited,result,i+1,j,root.children[c-'a'],curr+c,board);
            helper(visited,result,i,j-1,root.children[c-'a'],curr+c,board);
            helper(visited,result,i,j+1,root.children[c-'a'],curr+c,board);
        }
        visited[i][j]=false;//记得这是一个backtracking的过程，访问结束还原变量，这个是坑点
    }
    //Trie数据结构
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
    }
    private void insert(String word) {
        TrieNode curr = root;
        for(char c:word.toCharArray()){
            if(curr.children[c-'a']==null) curr.children[c-'a']=new TrieNode();
            curr = curr.children[c-'a'];
        }
        curr.isWord=true;
    }
}

时间复杂度：构建trie时间复杂度 O(sum(len)) ,len 是每个word的长度。遍历所有元素匹配过程:O(M*N*len)??

421. Maximum XOR of Two Numbers in an Array

Medium

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [0]
Output: 0

Example 3:

Input: nums = [2,4]
Output: 6

Example 4:

Input: nums = [8,10,2]
Output: 10

Example 5:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127 

Constraints:

• 1 <= nums.length <= 2 * 105
• 0 <= nums[i] <= 231 - 1


class Solution {
    public int findMaximumXOR(int[] nums) {
        //建立Trie
        Trie root = new Trie();
        for( int num:nums ) build(num,root);
        int max = 0;
        //循环遍历所有元素，求出最优解
        for(int num:nums){
            max = Math.max(max,xor(num,root));
        }
        return max;
    }
    //Trie 数据结构
    class Trie{
        Trie[] children = new Trie[2];
    }
    //建立 Trie
    private void build(int num,Trie root){
        for(int i=31;i>=0;i--){
            int res = (num>>i)&1;
            if(root.children[res]==null) root.children[res]=new Trie();
            root = root.children[res];
        }
    }
    //从trie中取出当前num xor的最优解
    private int xor(int num,Trie root){
        int sum = 0;
        for(int i=31;i>=0;i--){
            int res = (num>>i)&1;
            int resMax = res==1 ? 0 : 1;
            if(root.children[resMax]!=null){
                sum+=1<<i;
                root = root.children[resMax];
            }
            else
                root = root.children[res];
        }
        return sum;
    }
}

 

386. Lexicographical Numbers

Medium

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

You must write an algorithm that runs in O(n) time and uses O(1) extra space. 

Example 1:

Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2:

Input: n = 2
Output: [1,2] 

Constraints:

• 1 <= n <= 5 * 104


class Solution {
    public List lexicalOrder(int n) {
        Trie root = new Trie();
        for(int i=1;i<=n;i++) buildTrie(i,root);
        List result = new ArrayList();
        traversalTrie(root,result,0);
        return result;
    }
    private void traversalTrie(Trie trie,List list,int sum){
        if(trie.isNumber) list.add(sum);
        for(int i=0;i<10;i++){
            Trie child= trie.children[i];
            if(child==null) continue;
            traversalTrie(child,list,sum*10+i);
        }
    }
    class Trie{
        Trie[] children= new Trie[10];
        boolean isNumber;
    }
    private void buildTrie(int num,Trie root){
        Stack stack = new Stack();
        while(num>0){
            stack.push(num%10);
            num=num/10;
        }
        while(!stack.isEmpty()){
            int curr = stack.pop();
            if(root.children[curr]==null) root.children[curr] = new Trie();
            root=root.children[curr];
        }
        root.isNumber=true;
    }
}

1233. Remove Sub-Folders from the Filesystem

Medium

Given a list of folders folder, return the folders after removing all sub-folders in those folders. You may return the answer in any order.

If a folder[i] is located within another folder[j], it is called a sub-folder of it.

The format of a path is one or more concatenated strings of the form: '/' followed by one or more lowercase English letters.

• For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string and "/" are not. 

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b/" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d/" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

Constraints:

• 1 <= folder.length <= 4 * 104
• 2 <= folder[i].length <= 100
• folder[i] contains only lowercase letters and '/'.
• folder[i] always starts with the character '/'.
• Each folder name is unique.

class Solution {
    public List removeSubfolders(String[] folder) {
        //1.build
        Trie root = new Trie();
        for(String s:folder) build(root,s);
        //2.traverse
        List result = new ArrayList();
        traversal(root,result,"");
        return result;
    }
    private void traversal(Trie root,List result,String path){
        for(String key:root.children.keySet()){
            Trie val = root.children.get(key);
            if(val.isPath) result.add(path+"/"+key);
            else traversal(val,result,path+"/"+key);
        }
    }
    private void build(Trie root,String s){
        String[] arr = s.substring(1).split("/");
        for(String str:arr){
            Trie sub = root.children.get(str);
            if(sub==null) sub = new Trie();
            root.children.put(str,sub);
            root = sub;
        }
        root.isPath=true;
    }
    class Trie{
        Map children = new HashMap();
        boolean isPath;
    }
}