LeetCode：3291. 形成目标字符串需要的最少字符串数 I（Trie + dfs + 记忆化 Java）

目录

3291. 形成目标字符串需要的最少字符串数 I

题目描述：

实现代码与解析：

Trie + dfs + 记忆化

原理思路：

3291. 形成目标字符串需要的最少字符串数 I

题目描述：

        给你一个字符串数组 words 和一个字符串 target。

如果字符串 x 是 words 中 任意 字符串的 前缀，则认为 x 是一个 有效 字符串。

现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。

示例 1：

输入： words = ["abc","aaaaa","bcdef"], target = "aabcdabc"

输出： 3

解释：

target 字符串可以通过连接以下有效字符串形成：

• words[1] 的长度为 2 的前缀，即 "aa"。
• words[2] 的长度为 3 的前缀，即 "bcd"。
• words[0] 的长度为 3 的前缀，即 "abc"。

示例 2：

输入： words = ["abababab","ab"], target = "ababaababa"

输出： 2

解释：

target 字符串可以通过连接以下有效字符串形成：

• words[0] 的长度为 5 的前缀，即 "ababa"。
• words[0] 的长度为 5 的前缀，即 "ababa"。

示例 3：

输入： words = ["abcdef"], target = "xyz"

输出： -1

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 5 * 103
• 输入确保 sum(words[i].length) <= 105。
• words[i] 只包含小写英文字母。
• 1 <= target.length <= 5 * 103
• target 只包含小写英文字母。

实现代码与解析：

Trie + dfs + 记忆化

package test.形成目标字符串需要的最少字符串数3291;

class Solution {

    class Trie {

        Trie[] children = new Trie[26];
        // private boolean isEnd;
        void insert(String word) {

            Trie tmp = this;
            for (int i = 0; i < word.length(); i++) {
                int j = word.charAt(i) - 'a';
                if (tmp.children[j] == null) {
                    tmp.children[j]= new Trie();
                }
                tmp = tmp.children[j];
            }
            // tmp.isEnd = true;
        }
    }

    Trie trie = new Trie();

    Integer[] f;
    public int minValidStrings(String[] words, String target) {

        for (String word : words) {
            trie.insert(word);
        }
        f = new Integer[target.length()];
        int res = dfs(0, target.toCharArray());
        return res < 0x3f3f3f3f ? res : -1;
    }

    private int dfs(int cur, char[] cs) {
        if (cur >= cs.length) return 0;
        if (f[cur] != null) return f[cur];

        Trie node = trie;

        f[cur] = 0x3f3f3f3f;
        for (int i = cur; i < cs.length; i++) {
            int k = cs[i] - 'a';
            if (node.children[k] == null) break;
            f[cur] = Math.min(f[cur], dfs(i + 1, cs) + 1);
            node = node.children[k];

        }
        return f[cur];
    }
}

原理思路：

        trie树记录前缀，遍历target来dfs搜索，f数组记忆化避免重复计算。

f[i]表示，第i个字符开始后面需要的字符串个数。

• 通过一个循环，从当前位置 cur 开始遍历目标字符串的剩余部分（索引范围为 cur 到 cs.length - 1）。在循环中，首先计算当前字符在字典树节点子节点数组中的索引 int k = cs[i] - 'a';，若 node.children[k] 为 null，表示当前路径在字典树中无法继续匹配下去了，直接跳出循环。
• 接着更新 f[cur] 的值，取当前值和通过递归调用 dfs(i + 1, cs)（表示继续搜索下一个位置，且因为使用了一个额外的字符串，所以要加 1）的结果中的较小值，即 f[cur] = Math.min(f[cur], dfs(i + 1, cs) + 1);，然后将当前节点指针移动到对应的子节点 node = node.children[k];，继续下一轮循环搜索。
• 最后返回 f[cur] 的值，也就是当前位置开始匹配目标字符串所需要的最少字符串数量。