677. Key-value mapping: Trie application in conjunction with DFS

“This is the 14th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

Topic describes

This is 677. Key value mapping on LeetCode, medium difficulty.

Tag: “dictionary tree”, “DFS”, “hash table”

Implement a MapSum class with two methods, insert and sum:

• MapSum()Initialize theMapSumobject
• void insert(String key, int val)insertkey-valKey-value pairs, strings representing keyskey, integers represent valuesval. If the keykeyAlready exists, the original key-value pair will be replaced by the new key-value pair.
• int sum(string prefix)Returns all prefixes with that prefixprefixAt the beginning of keykeyThe sum of the values of.

Example:

Input: [" MapSum ", "insert", "sum", "insert", "sum"] [[], [" apple ", 3], [" ap "], [" app ", 2], [" ap "]] output: [null, null, 3, null, 5] MapSum = new MapSum(); mapSum.insert("apple", 3); mapSum.sum("ap"); // return 3 (apple = 3) mapSum.insert("app", 2); mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)Copy the code

Tip:

• 1 <= key.length, prefix.length <= 50
• key 和 prefixContains only lowercase English letters
• 1 <= val <= 1000
• Most call50 次 insert 和 sum

Trie + DFS

TrieTrieTrie is a tree of prefixes that can be added to a string. TrieTrieTrie is a tree of prefixes. TrieTrieTrie is a tree of prefixes that can be added to a string.

Consider how to implement two operations:

• Insert: Extends the basic TrieTrieTrie insert operation. The only difference from a regular insert operation is that it does not simply record the end of the word, but also the number of valvalval corresponding to the keykeykey. We can use hashhashHash int instead of Boolean isWordisWordisWord;

• Sum: Searches the dictionary tree for the input parameter prefixprefixPrefix. After reaching the end, DFS is used to search all subsequent schemes and sum the results.

Code:

class MapSum {
    int[][] tr = new int[2510] [26];
    int[] hash = new int[2510];
    int idx;
    public void insert(String key, int val) {
        int p = 0;
        for (int i = 0; i < key.length(); i++) {
            int u = key.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
        hash[p] = val;
    }
    public int sum(String prefix) {
        int p = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int u = prefix.charAt(i) - 'a';
            if (tr[p][u] == 0) return 0;
            p = tr[p][u];
        }
        return dfs(p);
    }
    int dfs(int p) {
        int ans = hash[p];
        for (int u = 0; u < 26; u++) {
            if(tr[p][u] ! =0) ans += dfs(tr[p][u]);
        }
        returnans; }}Copy the code

• Time complexity: let
  $key$The maximum length of is
  $n$, the maximum number of calls is
  $m$, character set size is
  $C$Ontology (
  $C$Fixed for
  $26$),insertThe operation complexity is
  $O(n)$; fromDFSFrom the perspective ofsumThe operation complexity is
  $O(C^n)$, but in fact, there is a clear computational upper bound for this problem, and the complexity of searching all the cells is
  $O(n * m * C)$
• Space complexity: O(n∗m∗C)O(n * m * C)O(n∗m∗C)

The last

This is the No.677 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks, so we will finish all the topics without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.