[单词拆分] 现有一份字典, 它包含若干个单词. 再给一串字符串

例子:
字典: ["welcome", "to", "tobe", "bei", "jing", "beijing"]
字符串: "welcometobeijing"
正确拆分结果: "welcome", "to", "beijing"
错误拆分结果: "welcome", "to", "bei", "jing"

分析:
对于给定的字符串 str, 我们考察长度为 n 的子串 str.substring(0, n) 的情况. 若该子串能够拆分, 我们设 OPT(n) 为该子串的最优拆分方案. 很明显, 整个字符串若能拆分, 则其最优方案为 OPT(str.length).
当然, 上面说的最优拆分方案, 指的是该方案拆分出的单词数是最少的.
我们假设, 所有长度小于 n 且能拆分的子串, 我们都已得到了其最优拆分方案. 同时规定长度为 0 的子串, 其最优拆分方案就是包含 0 个单词, 即 OPT(0) = 0. 基于这个假设, 我们来求解长度为 n 的子串的拆分方案.
我们知道, 若 str.substring(0, n) 能够拆分, 那么它一定能够表示成某个更小的能够拆分的子串再加上一个单词的形式, 例如若 "welcometobei" 能够拆分, 那么它可以表示成 "welcometo" 加 "bei" 的形式, 再如 "welcome" 可以表示成 "" 加 "welcome" 的形式.
假设有单词 a, b, c, 子串 str.substring(o, n) 可以表示成 str.substring(0, n - a.length) 加 a 的形式, 或者 str.substring(0, n - b.length) 加 b 的形式, 或者 str.substring(0, n - c.length) 加 c 的形式. 那么此时 str.substring(0, n) 的最优拆分方案是什么呢? 很显然, 以上三种表示形式中, 谁的单词数最少, 谁就是最佳拆分方案.
于是我们得到如下递推公式:
OPT(n) = min{OPT(n - a.length), OPT(n - b.length), OPT(n - c.length), ...} + 1
知道了这个公式, 再加上 OPT(0) = 0 的设定, 我们就可以一步步地推导出整个子串的最优拆分方案了.

代码实现:
若输入字符串长度为 n, 字典的单词数为 k, 以下实现的时间复杂度为 O(nk).

public class Test {

    public static void main(String[] args) {
        String str = "welcometobeijingtobe";
        HashSet<String> dict = new HashSet<>();
        Collections.addAll(dict, "jing", "bei", "beijing", "be", "tobe", "to", "welcome", "wel", "come");

        List<String> result = breakToWords(str, dict);
        System.out.println(result);
    }

    @SuppressWarnings("unchecked")
    public static List<String> breakToWords(String str, Set<String> dict) {
        // temp的初始容量可根据实际情况调整, 例如 句长/平均单词长度
        HashMap<Integer, LinkedList<String>> temp = new HashMap<>(str.length() >> 1);
        temp.put(0, new LinkedList<>());

        for (int i = 0; i < str.length(); i++) {
            LinkedList<String> matchedWordList = temp.get(i);
            if (Objects.isNull(matchedWordList)) {
                continue;
            }

            String remainStr = str.substring(i);
            for (String word : dict) {
                if (remainStr.startsWith(word)) {
                    int _i = i + word.length();
                    LinkedList<String> _matchedWordList = temp.get(_i);
                    if (Objects.isNull(_matchedWordList) || _matchedWordList.size() > matchedWordList.size() + 1) {
                        _matchedWordList = (LinkedList<String>) matchedWordList.clone();
                        _matchedWordList.add(word);
                        temp.put(_i, _matchedWordList);
                    }
                }
            }
        }

        LinkedList<String> result = temp.get(str.length());
        return Objects.nonNull(result) ? result : new LinkedList<>();
    }
}