9.22号刷题

208. Implement Trie (Prefix Tree)

题目描述

实现字典树，包含插入，查找和前缀查找方法。

注意：

你可以假设所有的输入只包含小写字母a-z

算法

利用Trie对这题进行求解，求解的过程中注意TrieNode的写法

class Trie {
    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        this.root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode cur = root;
        if (word == null || word.length() == 0) return;
        for (char c : word.toCharArray()) {
            if (!cur.containsKey(c)) {
                cur.put(c, new TrieNode());
            }
            cur = cur.get(c);
        }
        cur.setEnd();
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        if (word == null || word.length() == 0) return false;
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (!cur.containsKey(c)) return false;
            cur = cur.get(c);
        }
        return cur.isEnd();
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.length() == 0) return false;
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            if (!cur.containsKey(c)) {
                return false;
            }
            cur = cur.get(c);
        }
        return true;
    }
}

class TrieNode {
    private TrieNode[] links;
    private final int R = 26;
    private boolean isEnd;

    public TrieNode() {
        links = new TrieNode[R];
    }
    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }
    public TrieNode get(char ch) {
        return links[ch - 'a'];
    }
    public void put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
    }
    public void setEnd() {
        isEnd = true;
    }
    public boolean isEnd() {
        return isEnd;
    }
}

677. Map Sum Pairs

题目描述

设计一个数据结构MapSum，支持insert和sum操作。

insert(key, val)：向MapSum中插入一个key，对应一个val（当key存在时，替换对应的val）

sum(prefix)：求MapSum中对应前缀为prefix的所有key的val之和

算法

这题由于需要用到prefix，所以仍然是用trie结构，需要注意的重点是：不单可以用array来对try节点进行存储，也可以是用map来对trie进行存储

class MapSum {

    Map<String, Integer> map;
    TrieNode root;
    /** Initialize your data structure here. */
    public MapSum() {
        root = new TrieNode();
        map = new HashMap<>();
    }
    
    public void insert(String key, int val) {
        int delta = map.getOrDefault(key, 0);
        delta = val - delta;
        map.put(key, val);
        TrieNode cur = root;
        cur.sum += delta;
        for (char c : key.toCharArray()) {
            if (!cur.children.containsKey(c)) {
                cur.children.put(c, new TrieNode());
            }
            cur = cur.children.get(c);
            cur.sum += delta;
        }
    }
    
    public int sum(String prefix) {
        if (prefix == null) return 0;
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            if (!cur.children.containsKey(c)) return 0;
            cur = cur.children.get(c);
        }
        return cur.sum;
    }
    
}

class TrieNode {
    Map<Character, TrieNode> children;
    int sum;
    public TrieNode() {
        children = new HashMap<>();
        sum = 0;
    }
}

648. Replace Words

题目描述

英文中，以较短的单词为前缀，可以构成较长的单词。此时前缀可以称为“词根”。

给定一组词根字典dict，一个句子sentence。将句中的单词换为字典中出现过的最短词根。

算法

利用Trie, 查看每一个词是否可以进行替换，如果能够替换，则进行替换

class Solution {
    //Question: length in a sentense is smaller
    Trie root;
    public String replaceWords(List<String> dict, String sentence) {
        if (sentence == null || sentence.length() == 0) return sentence;
        root = new Trie();
        build(dict);
        StringBuilder sb = new StringBuilder();
        int left = 0, right = 0;
        while (right < sentence.length()) {
            char c = sentence.charAt(right);
            if (c == ' ') {
                String word = sentence.substring(left, right);
                String sub = find(word);
                if (sub.length() == 0) sb.append(word + " ");
                else sb.append(sub + " ");
                left = right + 1;
            }
            right++;
        }
        // The last word
        String word = sentence.substring(left);
        String sub = find(word);
        if (sub.length() == 0) sb.append(word);
        else sb.append(sub);
        
        return sb.toString();
    }
    
    public String find(String word) {
        Trie cur = root;
        String res = "";
        for (char c : word.toCharArray()) {
            if (cur.isEnd) return res;
            if (cur.links[c - 'a'] == null) return "";
            res += c;
            cur = cur.links[c - 'a'];
        }
        return "";
    }
    
    public void build(List<String> dict) {
        for (String word : dict) {
            Trie cur = root;
            for (char c : word.toCharArray()) {
                if (cur.links[c - 'a'] == null) {
                    cur.links[c - 'a'] = new Trie();
                }
                cur = cur.links[c - 'a'];
            }
            cur.isEnd = true;
        }
    }
    
}
class Trie {
    Trie[] links;
    boolean isEnd;
    public Trie() {
        links = new Trie[26];
        isEnd = false;
    }
}

676. Implement Magic Dictionary

题目描述

实现数据结构“魔法字典”，支持两种操作：

buildDict：输入一组无重复的单词，构建一个字典

search：在字典中寻找目标串，目标串与搜索串恰好有一个字符不同

算法

遇到这种问题，首先问一下是插入多还是搜索多。如果搜索多，尽量用将搜索的时间简短。

HashSet 搜索较快

Build: O(m * n)
Search: O(1)

class MagicDictionary {
    Set<String> candidates;
    /** Initialize your data structure here. */
    public MagicDictionary() {
        candidates = new HashSet<>();
    }
    
    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
        for (String word : dict) {
            for (int i = 1; i <= word.length(); i++) {
                char c = word.charAt(i - 1);
                for (char j = 'a'; j <= 'z'; j++) {
                    if (j == c) continue;
                    candidates.add(word.substring(0, i - 1) + j + word.substring(i));
                }
            }
        }
    }
    
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    public boolean search(String word) {
        return candidates.contains(word);
    }
}