820. Short Encoding of Words
Posted Updated LeetCode / Medium4 minutes read (About 596 words)

820. Short Encoding of Words

Question

A valid encoding of an array of words is any reference string s and array of indices indices such that:

  • words.length == indices.length
  • The reference string s ends with the '#' character.
  • For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i].

Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.

Solution 1

LeetCode这几天的每日一题时不让我学会字典树势不罢休啊……

字典树，参数isLeaf记录每个TireNode节点是否为叶子节点。
将单词倒序组建字典树，并维护isLeaf的属性。

计算从根节点到达每个叶子节点的长度再加一的和即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    class TrieNode{
        TrieNode[] next = new TrieNode[26];
        boolean isLeaf;
    }
    TrieNode root;
    int count;
    
    public int minimumLengthEncoding(String[] words) {        
        count = 0;
        root = new TrieNode();
        
        for(String word : words){
            add(word);
        }
        countLeaves(root, 0);
        return count;
    }
    
    private void add(String word){
        TrieNode curr = root;
        for(int i = word.length()-1; i >= 0; i--){
            int index = word.charAt(i) - 'a';
            if(curr.next[index] == null){
                curr.isLeaf = false;
                curr.next[index] = new TrieNode();
                curr.next[index].isLeaf = true;
            }
            curr = curr.next[index];
        }
    }
    
    private void countLeaves(TrieNode root, int length){
        if(root.isLeaf){
            count += length + 1;
        } 
        else{
            for(int i = 0; i < 26; i++){
                if(root.next[i] != null) countLeaves(root.next[i], length+1);
            }
        }
    }
}

Solution 2

排序，将数组words根据单词倒序排序。
倒序构成字典树，如果展开新的字典树分支（创建新的TrieNode节点）则将count加入根节点到新节点的距离。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    class TrieNode{
        TrieNode[] next = new TrieNode[26];
        boolean end;
    }
    TrieNode root;
    int count;
    
    public int minimumLengthEncoding(String[] words) {
        Arrays.sort(words, new Comparator<String>(){
            public int compare(String a, String b){
                int i = a.length()-1, j = b.length()-1;
                while(i >= 0 && j >= 0){
                    int index = a.charAt(i) - b.charAt(j);
                    if(index == 0){
                        i--;
                        j--;
                    }
                    else{
                        return index;
                    }
                }
                return j - i;
            }
        });
        
        count = 0;
        root = new TrieNode();
        
        for(String word : words){
            add(word);
        }
        
        return count;
    }
    
    private void add(String word){
        TrieNode curr = root;
        int length = 1;
        boolean newTrieNode = false;
        for(int i = word.length()-1; i >= 0; i--){
            int index = word.charAt(i) - 'a';
            if(curr.next[index] == null){
                curr.next[index] = new TrieNode();
                newTrieNode = true;
            }
            curr = curr.next[index];
            length++;
        }
        curr.end = true;
        if(newTrieNode) count += length;
    }
}

Solution 3

倒序重组字符串并记录到reversedWords[]数组，然后根据字典顺序排序。
如果数组的上一个字符串不是下一个字符串的前缀，则加入上一个字符串的长度加一。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {    
    public int minimumLengthEncoding(String[] words) {
        String[] reversedWords = new String[words.length];
        int count = 0, index = 0;
        for(String word : words){
            reversedWords[index] = new StringBuffer(word).reverse().toString();
            index++;
        }
        
        Arrays.sort(reversedWords);
        for(int i = 0; i < words.length-1; i++){
            if(!reversedWords[i+1].startsWith(reversedWords[i])) count += reversedWords[i].length()+1;
        }
        count += reversedWords[words.length-1].length()+1;
        return count;
    }
}
1268. Search Suggestions System
Posted Updated LeetCode / Medium / 复习2 minutes read (About 366 words)

1268. Search Suggestions System

Question

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Solution

字典树+优先级队列。
在TrieNode节点中保存PriorityQueue，以记录该节点下的三个单词。
注意PriorityQueue中的String需要按倒序排列，以保证维护时可以直接poll掉字符顺序较后的单词。

add()方法

创建并添加TrieNode节点，同时在移动当前节点位置时，需要维护PriorityQueue，当长度大于3时，则挤出字典顺序排列较后的单词。

search()方法

在查找前缀时，将每个TrieNode节点上的PriorityQueue倒序加入List。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    class TrieNode{
        boolean end;
        TrieNode[] children = new TrieNode[26];
        PriorityQueue<String> q = new PriorityQueue<>((a, b) -> b.compareTo(a));
    }
    
    TrieNode root;
    
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> ret = new ArrayList<>();
        root = new TrieNode();
        for(String word : products){
            add(word);
        }
        return search(searchWord);
    }
    
    private void add(String word){
        TrieNode curr = root;
        for(char c : word.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
            curr.q.add(word);
            if(curr.q.size() > 3) curr.q.poll();
        }
        curr.end = true;
    }
    
    private List<List<String>> search(String prefix){
        List<List<String>> ret = new ArrayList<>();
        TrieNode curr = root;
        for(char c : prefix.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
            List<String> temp = new ArrayList<>();
            while(!curr.q.isEmpty()){
                temp.add(curr.q.poll());
            }
            Collections.reverse(temp);
            ret.add(temp);
        }
        return ret;
    }
}
745. Prefix and Suffix Search
Posted Updated Hard / 复习4 minutes read (About 570 words)

745. Prefix and Suffix Search

Question

Design a special dictionary with some words that searchs the words in it by a prefix and a suffix.

Implement the WordFilter class:

  • WordFilter(string[] words) Initializes the object with the words in the dictionary.
  • f(string prefix, string suffix) Returns the index of the word in the dictionary, which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.

Solution

改版的前缀树，用后缀+符号+前缀的形式记录字典树。

TrieNode

用参数id记录TrieNode经历过的最大下标。

27位TrieNode数组children[]记录子TrieNode。

初始化

将words[]中的每个字符串记录在TrieNode上，保存TrieNode的根节点root。
在遍历每个字符串时，需要将每个“后缀+符号+前缀”组成的新字符串记录在字典树中，并更新当前节点的id值。

将后缀部分添加完毕后，加入特殊符号。检查并创建当前节点的curr[26]位置。
然后继续将整个前缀字符串加入字典树，并更新当前节点的id值。

搜索

搜索时，先遍历后缀，查找字典树的路径是否存在，并更新当前节点的位置，如不存在则返回-1。
然后检查并跳过curr.children[26]的位置，如不存在则返回-1。
最后遍历前缀，更新节点位置，如果路径不存在则返回-1。

最后返回当前节点的id即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class WordFilter {
    class TrieNode{
        int id;
        TrieNode[] children;
        public TrieNode(){
            children = new TrieNode[27];
            id = 0;
        }
    }
    
    TrieNode root;
    public WordFilter(String[] words) {
        root = new TrieNode();
    
        for(int k = 0; k < words.length; k++){
            String word = words[k];
            for(int i = 0; i < word.length(); i++){
                TrieNode curr = root;
                int j = i;
                while(j < word.length()){
                    int index = word.charAt(j) - 'a';
                    if(curr.children[index] == null) curr.children[index] = new TrieNode();
                    curr = curr.children[index];
                    curr.id = k;
                    j++;
                }
                if(curr.children[26] == null) curr.children[26] = new TrieNode();
                curr = curr.children[26];
                curr.id = k;
                for(char c : word.toCharArray()){
                    int index = c - 'a';
                    if(curr.children[index] == null) curr.children[index] = new TrieNode();
                    curr = curr.children[index];
                    curr.id = k;
                }
            }
        }
    }
    
    public int f(String prefix, String suffix) {
        TrieNode curr = root;
        for(char c : suffix.toCharArray()){
            int index = c - 'a';
            if(curr.children[index] == null) return -1;
            curr = curr.children[index];
        }
        
        if(curr.children[26] == null) return -1;
        curr = curr.children[26];
        
        for(char c : prefix.toCharArray()){
            int index = c - 'a';
            if(curr.children[index] == null) return -1;
            curr = curr.children[index];
        }
        return curr.id;
    }
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(prefix,suffix);
 */
208. Implement Trie (Prefix Tree)
Posted Updated Medium / 复习4 minutes read (About 600 words)

208. Implement Trie (Prefix Tree)

Question

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.

Solution

参考：实现 Trie :「二维数组」&「TrieNode」方式

前缀树，字典树结构实现。

前缀树 Trie

前缀树结构用“边”记录有无字符，用“点”记录单词结尾以及后续的字符串字符。
root节点记录字典的根节点。

TrieNode节点

用TrieNode节点实现前缀树。
真值end记录是否为字符串的结尾，创建时默认为false。
数组TrieNode[] children记录子节点。

insert()方法

从根节点root开始，遍历字符串。
如果对应的子节点位置为空，则创建新的TrieNode节点。
向下移动当前节点。

将最后一个节点设置为end，使得整个字符串被字典记录。

search()方法

从根节点root开始，遍历字符串。
如果子节点位置为空，则这个字符串不在字典中，返回false。
否则向下移动当前节点。

遍历完毕，如果当前节点的end为true，则存在该字符串，返回true。

startsWith()方法

从根节点root开始，遍历前缀字符串。
如果子节点位置为空，则这个前缀不在字典中，返回false。
否则向下移动当前节点。

最后返回true。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Trie {
    class TrieNode {
        boolean end;
        TrieNode[] children = new TrieNode[26];
    }
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode curr = root;
        for(char c : word.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
        }
        curr.end = true;
    }
    
    public boolean search(String word) {
        TrieNode curr = root;
        for(char c : word.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) return false;
            curr = curr.children[i];
        }
        return curr.end;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for(char c : prefix.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) return false;
            curr = curr.children[i];
        }
        return true;
    }
    
    
}

/**
 * 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);
 */
968. Binary Tree Cameras
Posted Updated Hard / 复习10 minutes read (About 1452 words)

968. Binary Tree Cameras

Question

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

Return the minimum number of cameras needed to monitor all nodes of the tree.

Solution 1

贪心算法，后序遍历。每次递归根据下面两个子节点的状态来决定当前节点的状态。

每个节点一共有三种状态：

  1. 未被监控，返回0。
  2. 摄像头，返回1。
  3. 已被监控，返回2。

递归，当当前节点为空，则返回2，表示已被监控。这样叶子节点则为未被监控的状态。

如果下面的子节点有一个未被监控，则当前节点需要设置相机，返回1，计数res+1。
如果下面的子节点有一个为摄像头，则当前节点已被监控，返回2。
否则下面的节点均为已被监控，此时返回未被监控0。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0; //记录摄像头个数
    public int minCameraCover(TreeNode root) {
        if(judge(root) == 0) res++;  //如果根节点未被监控，则需要增加一个摄像机
        return res;
    }
    public int judge(TreeNode root){
        if(root == null) return 2;   //根节点为空时返回2，这样叶子节点变为未被监控
        int left = judge(root.left);
        int right = judge(root.right);

        if(left == 0 || right == 0){    //如果左右子节点有未被监控的节点，则当前节点设置为摄像机，结果加一，返回1
            res++;
            return 1;
        }
        if(left == 1 || right == 1) return 2;    //如果左右子节点中有摄像机，则当前节点已被监控，返回2
        return 0;   //如果左右子节点都被监控，则当前节点未被监控，返回0
    }
}

Solution 2

参考：从递归优化到树形DP

树形DP。
递归，每次返回当前节点所有子节点的最小相机数。
每一个节点有三种状态：

  1. 放置了相机。
  2. 没有相机，但是被父节点parent监控。
  3. 没有相机，但是被子节点son监控。

将三种状态分别传入minCam()方法。

递归方法 minCam()

在递归时传入两个参数hasCamera和isWatched，来判断当前节点是否有相机，是否被监控。
当当前节点为空节点时，如果设置应当有相机（做不到）则返回无限大，消除这个返回值。如果不应该有相机，则返回0。

向下递归子节点。

  • 当当前节点应该有相机时：
    子节点一定被监控因此isWatched为true。
    子节点可以放置或不放置相机，因此hasCamera可以为true或false。
    注意当前位置放置相机，则子节点最多放置一个相机，因此一共有三种组合。
    由于相机至少有一个，因此返回其中的最小值+1。
  • 当当前节点没有放置相机，但被父节点监控时：
    左右节点一共有四种组合，分别同时将子节点的监控状态向下递归。
    返回其中的最小值。
  • 当当前节点没有放置相机，也没有被父节点监控，而是被子节点监控时：
    子节点至少有一个相机，向下递归状态，一共有三种组合。
    返回其中的最小值

然后分别调用minCam(root, true, true)和minCam(root, false, fasle)，取两者中的小值，即可得到答案。

树形dp优化剪枝

上面的方法实际采用时会超时，因为我们重复了三次调用一个子树下的三种状态的minCam。
因此我们可以将三种状态下的minCam分别保存在数组中返回。

  1. withCam: 当前子树root有相机。
  2. noCamWatchedByParent: 当前子树root没有相机，被父节点监控。
  3. noCamWatchedBySon: 当前子树root没有相机，被子节点监控。

在每次递归时，获取数组minCam(root.left)和minCam(root.right)。
然后根据左右子节点的三个参数来计算当前节点的新的三个参数，将其返回。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        return Math.min(minCam(root, true, true), minCam(root, false, false));
    }
    
    private int minCam(TreeNode root, boolean hasCamera, boolean isWatched){
        if(root == null) return hasCamera ? Integer.MAX_VALUE / 2 : 0;

        if(hasCamera){
            int min = Math.min(minCam(root.left, false, true) + minCam(root.right, false, true), minCam(root.left, true, true) + minCam(root.right, false, true));
            min = Math.min(min, minCam(root.left, false, true) + minCam(root.right, true, true));
            return 1 + min;
        }
        else if(isWatched){
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, false, false));
            return min;
        }
        else{
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            return min;
        }
    }
}

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        int[] res = minCam(root);
        return Math.min(res[0], res[2]);
    }
    
    private int[] minCam(TreeNode root){
        if(root == null){
            return new int[] {Integer.MAX_VALUE/2, 0, 0};
        }
        int[] left = minCam(root.left);
        int[] right = minCam(root.right);

        int withCam = 1 + Math.min(left[1] + right[1], Math.min(left[0] + right[1], left[1] + right[0]) );
        int noCamWatchedByParent = Math.min( left[0] + right[0], Math.min( left[0] + right[2], Math.min( left[2] + right[0], left[2] + right[2] )));
        int noCamWatchedBySon = Math.min( left[0] + right[0], Math.min( left[0] + right[2], left[2] + right[0]));
        return new int[] {withCam, noCamWatchedByParent, noCamWatchedBySon};
    }
}
Follow

Recents

Archives

Links

×