3291. Minimum Number of Valid Strings to Form Target I

Posted on Edited on In

3291. Minimum Number of Valid Strings to Form Target I

Description

You are given an array of strings words and a string target.

A string x is called valid if x is a prefix of any string in words.

Return the minimum number of valid strings that can be concatenated to form target. If it is not possible to form target, return -1.

Example 1:

1
2
3
Input: words = ["abc","aaaaa","bcdef"], target = "aabcdabc"

Output: 3

Explanation:

The target string can be formed by concatenating:

  • Prefix of length 2 of words[1], i.e. "aa".
  • Prefix of length 3 of words[2], i.e. "bcd".
  • Prefix of length 3 of words[0], i.e. "abc".

Example 2:

1
2
3
Input: words = ["abababab","ab"], target = "ababaababa"

Output: 2

Explanation:

The target string can be formed by concatenating:

  • Prefix of length 5 of words[0], i.e. "ababa".
  • Prefix of length 5 of words[0], i.e. "ababa".

Example 3:

1
2
3
Input: words = ["abcdef"], target = "xyz"

Output: -1

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 5 * 10^3
  • The input is generated such that sum(words[i].length) <= 10^5.
  • words[i] consists only of lowercase English letters.
  • 1 <= target.length <= 5 * 10^3
  • target consists only of lowercase English letters.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    struct TrieNode {
        vector<TrieNode*> children;
        TrieNode() {
            children = vector<TrieNode*>(26, nullptr);
        }
    };
    TrieNode* root;
    string target_;
    unordered_map<int, int> dp;

    int minValidStrings(vector<string>& words, string target) {
        root = new TrieNode();
        target_ = target;
        // dp.resize(target.size(), INT_MAX);
        for (string word : words) {
            TrieNode* cur = root;
            for (char c : word) {
                if (!cur->children[c - 'a']) {
                    cur->children[c - 'a'] = new TrieNode();
                }
                cur = cur->children[c - 'a'];
            }
        }
        int res = dfs(0);
        return res == INT_MAX ? -1 : res;
    }

    int dfs(int index) {
        if (index == target_.size()) {
            return 0;
        }
        if (dp.contains(index)) {
            return dp[index];
        }
        long res = INT_MAX;
        TrieNode* cur = root;
        int end = index;
        for (end = index; end < target_.size() && cur; end++) {
            cur = cur->children[target_[end] - 'a'];
            if (!cur) {
                break;
            }
        }
        // two cases the end stop:
        //  1. the end reaches the end of target
        //  2. the cur is not valid, so cur is valid at end - 1
        //     and we can only matches [index, end - 2]
        if (end == target_.size() && cur) {
            res = 1;
        } else {
            for (int i = end - 1; i >= index; i--) {
                res = min(res, (long)dfs(i + 1) + 1);
            }
        }
        dp[index] = res;
        return res;
    }
};