面试题 17.13. 恢复空格

解法一：直接DP

参考链接：https://leetcode-cn.com/problems/re-space-lcci/solution/jian-dan-dp-trieshu-bi-xu-miao-dong-by-sweetiee/ 解法一

import java.util.HashSet;
import java.util.Set;
class Solution {
    public int respace(String[] dictionary, String sentence) {
        Set<String> dictionatySet = new HashSet<>(dictionary.length);
        for (String str : dictionary) {
            dictionatySet.add(str);
        }
        int len = sentence.length();
        int[] dp = new int[len + 1];
        for (int i = 1; i <= len; ++i) {
            dp[i] = dp[i - 1] + 1;
            for (int j = 0; j < i; ++j) {
                if (dictionatySet.contains(sentence.substring(j, i))) {
                    dp[i] = Math.min(dp[i], dp[j]);
                }
            }
        }
        return dp[len];
    }
}

解法二：Trie加速查询

参考链接：https://leetcode-cn.com/problems/re-space-lcci/solution/jian-dan-dp-trieshu-bi-xu-miao-dong-by-sweetiee/ 解法二

import java.util.*;
class Solution {
    public int respace(String[] dictionary, String sentence) {
        Trie trie = new Trie();
        for (String str : dictionary) {
            StringBuilder stringBuilder = new StringBuilder(str);
            trie.add(stringBuilder.reverse().toString());
        }
        int len = sentence.length();
        int[] dp = new int[len + 1];
        for (int i = 1; i <= len; ++i) {
            dp[i] = dp[i - 1] + 1;
            for (int j : trie.search(sentence, i - 1)) {
                dp[i] = Math.min(dp[i], dp[j]);
            }
        }
        return dp[len];
    }
}
/**
 * 字典树， 以实现基本的增删查操作
 */
class Trie {
    /**
     * 根结点
     */
    private Node root;
    /**
     * 单词数量
     */
    private int size;
    public Trie() {
        root = new Node();
    }
    /**
     * 添加单词
     *
     * @param word 单词
     */
    public void add(String word) {
        Node p = root;
        for (char ch : word.toCharArray()) {
            if (p.next.get(ch) == null) {
                p.next.put(ch, new Node());
            }
            p = p.next.get(ch);
        }
        // 该节点上没有单词则加上单词
        // 防止相同单词重复添加
        if (!p.isWord) {
            p.isWord = true;
            ++size;
        }
    }
    /**
     * 查询在s中以end下标为字符串结尾的子串且它在Trie中
     *
     * @param s   源字符串
     * @param end 结尾字符下标
     * @return 符合条件的单词数组
     */
    public List<Integer> search(String s, int end) {
        List<Integer> ans = new LinkedList<>();
        Node p = root;
        for (int i = end; i >= 0; --i) {
            char ch = s.charAt(i);
            if (p.next.get(ch) == null) {
                break;
            }
            p = p.next.get(ch);
            if (p.isWord) {
                ans.add(i);
            }
        }
        return ans;
    }
}
/**
 * 字符结点
 */
class Node {
    /**
     * 当前结点是否为某个单词的结尾
     */
    public boolean isWord;
    /**
     * 用Map存储子结点
     */
    public Map<Character, Node> next;
    public Node() {
        next = new HashMap<>();
    }
    public Node(boolean isWord) {
        this.isWord = isWord;
    }
}