🟡 剑指 Offer II 063. 替换单词

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解1

class Trie {    public Trie[] child;    public boolean isEnd;
    public Trie() {        this.child = new Trie[26];        this.isEnd = false;    }
    public Trie appendChild(char c) {        if (this.child[c-'a'] == null) {            this.child[c-'a'] = new Trie();        }        return this.child[c-'a'];    }
    public Trie getChild(char c) {        return this.child[c-'a'];    }
    public void end() {        this.isEnd = true;    }
    public void appendPrefix(String word) {        Trie cur = this;        for (char c : word.toCharArray()) {            cur = cur.appendChild(c);        }        cur.end();    }
    public String prefix(String word) {        Trie cur = this;        StringBuilder sb = new StringBuilder();        for (char c : word.toCharArray()) {            cur = cur.getChild(c);            if (cur == null) {                return word;            }            sb.append(c);
            if (cur.isEnd) {                return sb.toString();            }        }        return word;    }}
class Solution {    public String replaceWords(List<String> dictionary, String sentence) {        Trie root = new Trie();        for (String dic : dictionary) {            root.appendPrefix(dic);        }
        String[] swords = sentence.split(" ");
        for (int i=0; i<swords.length; i++) {            String pre = root.prefix(swords[i]);            swords[i] = pre;        }
        return String.join(" ", swords);    }}