LeetCode 648. 单词替换

648. 单词替换

【哈希+字符串处理】将dictionary中的单词放到HashSet中，在添加过程中记录单词的长度，方便对sentence中的单词取前缀。

class Solution {

    // 哈希+字符串截取 12:41

    public String replaceWords(List<String> dictionary, String sentence) {
        Set<String> set = new HashSet();
        Set<Integer> length = new HashSet();
        for (var st: dictionary) {
            set.add(st);
            length.add(st.length());
        }
        List<Integer> l = new ArrayList(length);
        Collections.sort(l);
        String[] strs = sentence.split(" ");
        int n = l.size();
        StringBuilder sb = new StringBuilder();
        for (var str: strs) {
            sb.append(" ");
            var flag = 0;
            for (var i = 0; i < n; i++) {
                var m = l.get(i);
                if (m >= str.length()) {
                    break;
                } else {
                    var st = str.substring(0, m);
                    if (set.contains(st)) {
                        flag = 1;
                        sb.append(st);
                        break;
                    }
                }
            }
            if (flag == 0) {
                sb.append(str);
            }
        }
        return sb.toString().strip();
    }
}

【字典树】对dictionary中的单词建树，遍历sentence中的单词，最先匹配到的前缀返回即可。

class Solution {

    // 字典树 1:15 33

    class Trie {
        Trie[] map = new Trie[26];
        boolean is_end;
    }
    Trie root = new Trie();

    public void add(String str) {
        Trie node = root;
        for (var i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (node.map[c - 'a'] != null) {
                node = node.map[c - 'a'];
            } else {
                Trie trie = new Trie();
                node.map[c - 'a'] = trie;
                node = trie;
            }
        }
        node.is_end = true;
    }

    public String pre(StringBuilder sb, String str) {
        Trie node = root;
        for (var i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (node.map[c - 'a'] == null) {
                return str;
            } else {
                sb.append(c);
                node = node.map[c - 'a'];
                if (node.is_end) {
                    return sb.toString();
                }
            }
        }
        return str;
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        for (var str: dictionary) {
            add(str);
        }
        String[] strs = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (var str: strs) {
            sb.append(pre(new StringBuilder(), str));
            sb.append(" ");
        }
        return sb.toString().strip();
    }
}

【字典树+哈希表写法】

class Solution {

    // 字典树 10:05 10:16

    class Trie {
        Map<Character, Trie> map = new HashMap();
        boolean endOfWord = false;
    }

    Trie root = new Trie();

    public void add(String str) {
        Trie node = root;
        for (var i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (node.map.containsKey(c)) {
                node = node.map.get(c);
            } else {
                Trie trie = new Trie();
                node.map.put(c, trie);
                node = trie;
            }
        }
        node.endOfWord = true;
    }

    public String prefix(String str) {
        Trie node = root;
        StringBuilder sb = new StringBuilder();
        for (var i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (node.map.containsKey(c)) {
                sb.append(c);
                node = node.map.get(c);
                if (node.endOfWord) {
                    return sb.toString();
                }
            } else {
                return str;
            }
        }
        return str;
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        for (var str: dictionary) {
            add(str);
        }
        String strs[] = sentence.split(" ");
        for (var i = 0; i < strs.length; i++) {
            strs[i] = prefix(strs[i]);
        }
        return String.join(" ", strs);
    }
}