648. Word replacement: the classic application of dictionary tree

Title Description

This is a LeetCode Upper 648. Word substitution , The difficulty is secondary .

Tag : 「 Dictionary tree 」

In English , We have one called   Root (root) The concept of , You can add other words after the root to form another longer word —— We call it   Inheritance words (successor). for example , Root an, Follow the word  other( other ), Can form new words  another( the other one ).

Now? , Given a dictionary consisting of many roots dictionary And a sentence formed by separating words with spaces sentence. You need to replace all the inherited words in the sentence with roots . If an inherited word has many roots that can form it , Replace it with the shortest root .

You need to output the replaced sentences .

Example 1：

 Input ：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"

 Output ："the cat was rat by the bat"

Example 2：

 Input ：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"

 Output ："a a b c"

Tips ：

• dictionary[i]  It's only made up of lowercase letters .
• sentence  Only lowercase letters and spaces .
• sentence The total number of words in the range Inside .
• sentence The length of each word in the range Inside .
• sentence Words in are separated by a space .
• sentence  No leading or trailing spaces .

Basic analysis

This is a way Trie The template question of , I don't know yet Trie Students can look at the front ：【 Design data structure 】 Realization Trie ( Prefix tree )

In front of It explains Trie Structure and principle of , And provides two implementations Trie The way .

Back to the subject , For convenience , We make ds by dictionary, Make s by sentence.

Two dimensional array

A more customary practice , It's using 「 Two dimensional array 」 To achieve Trie, coordination static Optimize , Can effectively control new The number of times , The time consumption is relatively stable .

Consider two Trie Basic operation ：

• add operation ： Variable input parameter string s, Map each character in the string to , At the same time, in order to facilitate the query of a string （ Not just a prefix ） Have you ever deposited Trie in , Use an extra Boolean array isEnd Record whether a position is the end of a word .
• query operation ：

As for the size estimation of two-dimensional array , It can be opened directly , among To insert into Trie The total number of characters in , Is the corresponding character set size . stay No, MLE At risk , You can drive so much directly ; And when more （ exceed , even to the extent that when ）, You can properly Medium Reduce , Make the total space in about , Because in fact, more than one character will be stored in some lines of the two-dimensional array , In fact, we don't need so many lines .

Code （ Don't use static Optimize , It takes ten times longer ）：

class Solution {
    static int N = 100000, M = 26;
    static int[][] tr = new int[N][M];
    static boolean[] isEnd = new boolean[N * M];
    static int idx;
    void add(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
        isEnd[p] = true;
    }
    String query(String s) {
        for (int i = 0, p = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) break;
            if (isEnd[tr[p][u]]) return s.substring(0, i + 1);
            p = tr[p][u];
        }
        return s;
    }
    public String replaceWords(List<String> ds, String s) {
        for (int i = 0; i <= idx; i++) {
            Arrays.fill(tr[i], 0);
            isEnd[i] = false;
        }
        for (String d : ds) add(d);
        StringBuilder sb = new StringBuilder();
        for (String str : s.split(" ")) sb.append(query(str)).append(" ");
        return sb.substring(0, sb.length() - 1);
    }
}

• Time complexity ： Make , by s length , The complexity is
• Spatial complexity ： , among Is the character set size

TrieNode

Another can effectively avoid 「 Estimate the size of the array 」 How to operate , It's using TrieNode The way to achieve Trie： Trigger every time you use a new grid new operation .

As for why TrieNode The way , I will still use 「 Two dimensional array 」 Priority approach , stay You know A classmate asked me a similar question , But the original problem is 「 Why is there a dynamic open point segment tree , direct build Out The practice of space still makes sense 」, This corresponds to the use of 「 Two dimensional array 」 still 「TrieNode」 It's the same thing ：

Unless some languages start , In the way of virtual machine , And allocate enough memory in advance , Otherwise, all of them new Operations need to be reflected in os On , And in the linux When allocating, you need to traverse the red black tree , So even the total space is the same , disposable new It's smaller than many times new Save time , At the same time, it is centralized new It is also more dispersive new Operate faster , That's why we don't use mindlessly TrieNode Why .

Code ：

class Solution {
    class Node {
        boolean isEnd;
        Node[] tns = new Node[26];
    }
    Node root = new Node();
    void add(String s) {
        Node p = root;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) p.tns[u] = new Node();
            p = p.tns[u];
        }
        p.isEnd = true;
    }
    String query(String s) {
        Node p = root;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) break;
            if (p.tns[u].isEnd) return s.substring(0, i + 1);
            p = p.tns[u];
        }
        return s;
    }
    public String replaceWords(List<String> ds, String s) {
        for (String str : ds) add(str);
        StringBuilder sb = new StringBuilder();
        for (String str : s.split(" ")) sb.append(query(str)).append(" ");
        return sb.substring(0, sb.length() - 1);
    }
}

• Time complexity ： Make , by s length , The complexity is
• Spatial complexity ： , among Is the character set size

snacks

Today, I add an extra meal question that is more suitable for the written examination interview : combination DFS Of Trie Application questions

Last

This is us. 「 Brush through LeetCode」 The first of the series No.648 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases