题目

假设所有字符都是小写字母
大字符串是str
arr是去重的单词表, 每个单词都不是空字符串且可以使用任意次.
使用arr中的单词有多少种拼接str的方式. 返回方法数.

解题思路

该题为从左到右模型

步骤

基本思路就是以i位置为开头(假设前面的位置都拼接好了),有多少种拼接方法
我们遍历从i到i位置能不能拼接
i到i+1能不能拼接
i到i+2能不能拼接
....
i到N能不能拼接

    public static int ways(String str, String[] arr) {
        HashSet<String> set = new HashSet<>();
        for (String candidate : arr) {
            set.add(candidate);
        }
        return process(str, 0, set);
    }

    // 所有的可分解字符串，都已经放在了set中
    // str[i....] 能够被set中的贴纸分解的话，返回分解的方法数
    public static int process(String str, int i, HashSet<String> set) {
        if (i == str.length()) { // 没字符串需要分解了！
            return 1;
        }
        //  i....还有字符串需要分解
        int ways = 0;
        // [i ... end] 前缀串 每一个前缀串
        for (int end = i; end < str.length(); end++) {
            String pre = str.substring(i, end + 1);// [)
            if (set.contains(pre)) {
                ways += process(str, end + 1, set);
            }
        }
        return ways;
    }

方法中只有一个可变参数,这就是一个一维动态规划表

dp[i]:
str从i出发及其后面所有的字符串被set分解有几种方法
整张表都填完,0位置返回就是最终答案
复杂度O(N^3)
因为有前缀字符串的检查

优化

使用前缀树记录set的字符串,减少前缀字符串的检查代价

这个点他往下没有走向a的路了,你以后所有的前缀串都不用查了
每次查一个前缀串有没有,它就是在前缀树移动一个格子。而且如果没有路了,你可以直接返回

代码

    public static class Node {
        public boolean end;
        public Node[] nexts;

        public Node() {
            end = false;
            nexts = new Node[26];
        }
    }

    public static int ways3(String str, String[] arr) {
        if (str == null || str.length() == 0 || arr == null || arr.length == 0) {
            return 0;
        }
        Node root = new Node();
        for (String s : arr) {
            char[] chs = s.toCharArray();
            Node node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new Node();
                }
                node = node.nexts[index];
            }
            node.end = true;
        }
        return g(str.toCharArray(), root, 0);
    }

    // str[i...] 被分解的方法数，返回

    public static int g(char[] str, Node root, int i) {
        if (i == str.length) {
            return 1;
        }
        int ways = 0;
        Node cur = root;
        // i...end
        for (int end = i; end < str.length; end++) {
            int path = str[end] - 'a';
            if (cur.nexts[path] == null) {
                break;
            }
            cur = cur.nexts[path];
            if (cur.end) { // i...end
                ways += g(str, root, end + 1);
            }
        }
        return ways;
    }