• Leetcode POTDs

Problem 3291 Minimum Number of Valid Strings to Form Target I

Problem Statement

Link - Problem 3291

Question

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:

Example 2:

Example 3:

Constraints:

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

Solution

class TrieNode {
public:
    vector<TrieNode*> children;
    bool isEnd;

    TrieNode() : children(26, nullptr), isEnd(false) {}
};

class Solution {
private:
    TrieNode* root;

    void insert(const string& word) {
        TrieNode* node = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word[i] - 'a';
            if (!node->children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
            node->isEnd = true;
        }
    }

public:
    int minValidStrings(vector<string>& words, string target) {
        std::ios::sync_with_stdio(false);
        root = new TrieNode();
        for (const string& word : words) {
            insert(word);
        }

        int n = target.length();
        vector<int> dp(n + 1, INT_MAX - 1);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            if (dp[i] == INT_MAX - 1)
                continue;

            TrieNode* node = root;
            for (int j = i; j < n; j++) {
                int index = target[j] - 'a';
                if (!node->children[index])
                    break;

                node = node->children[index];
                if (node->isEnd) {
                    dp[j + 1] = min(dp[j + 1], dp[i] + 1);
                }
            }
        }

        return dp[n] == INT_MAX - 1 ? -1 : dp[n];
    }
};

Complexity Analysis

| Algorithm                     | Time Complexity | Space Complexity |
| ----------------------------- | --------------- | ---------------- |
| Dynamic programming with Trie | O(n log m + mn) | O(n)             |

Explanation

Intial Thoughts

Initial approach is to understand the characteristics of the given words and target strings, looking for patterns or prefixes in the words that could match the target. It seems like a problem where we need to find the shortest combination of valid prefixes from the given words to form the target. Using a Trie data structure could be helpful to store the words and efficiently check for prefixes. We also need to consider how to backtrack and try different combinations if the current path does not lead to the target.

Intuitive Analysis

Intuitively, we can think of this problem as a dynamic programming problem where we build up a solution from smaller sub-problems. We start with an empty target and gradually build it up by trying to match prefixes from the given words. We need to keep track of the minimum number of valid strings required to form the target so far. If we reach the end of the target and we have a valid combination, we can return the count. If not, we need to backtrack and try different combinations. This process can be optimized using a Trie data structure to efficiently store and retrieve prefixes.

1. Intuition

• The problem can be solved by using a Trie data structure to store the given words.
• The Trie allows us to efficiently check if a prefix of the target string is present in the words.
• We can use dynamic programming to build up the solution by checking all prefixes of the target string.
• The key insight is that a valid string can be formed by concatenating prefixes of the words in the Trie.
• We need to find the minimum number of valid strings that can be concatenated to form the target string.
• The problem can be solved in O(n*m) time complexity where n is the length of the target string and m is the total length of all words.
• The space complexity is O(m) for storing the Trie.

2. Implementation

• We create a TrieNode class to represent each node in the Trie, with a vector of children and a boolean to mark the end of a word.
• The insert function is used to insert each word into the Trie, setting the isEnd flag to true at the end of each word.
• We use a dynamic programming array dp to store the minimum number of valid strings that can be concatenated to form the target string up to each position.
• We initialize dp[0] to 0 and all other positions to INT_MAX - 1, indicating that it is not possible to form the target string up to that position.
• We iterate over the target string and for each position, we check all prefixes of the target string starting from that position.
• If a prefix is present in the Trie, we update dp[j + 1] to be the minimum of its current value and dp[i] + 1.
• Finally, we return dp[n] if it is not equal to INT_MAX - 1, indicating that it is possible to form the target string, otherwise we return -1.

Complexity Analysis

Time Complexity:

• The given code iterates through each string in the words array, resulting in O(m * n) operations, where m is the number of strings and n is the average length of a string.
• Additionally, the code has nested loops that traverse target, leading to O(n log m) operations where n is the target length and the log factor represents the average depth of the Trie.
• As a result, the overall time complexity is O(n log m + m * n), justifying the Big O classification since it represents the upper bound on the number of operations.

Space Complexity:

• The primary memory usage comes from the TrieNode’s children array and the dp array in the minValidStrings method.
• Each TrieNode’s children array takes up a constant amount of memory (O(26) to be precise), while the dp array requires O(n) space, where n is the target length.
• Considering all these factors, the space complexity justifies an assignment of O(n).

Footnote

This question is rated as Medium difficulty.

Hints

Let dp[i] be the minimum cost to form the prefix of length i of target.

If target[(i + 1)..j] matches any prefix, update the range dp[(i + 1)..j] to minimum between original value and dp[i] + 1.

Use a Trie to check prefix matching.

Similar Questions: