We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Valid Strings to Form Target II

Number: 3557

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of strings words and a string target, determine the minimum number of valid strings that can be concatenated together to form target. A string x is considered valid if x is a prefix of any string in words. Return the minimum number needed, or -1 if it is impossible to form the target string.

Key Insights

  • Every node in a Trie constructed from words represents a valid prefix.
  • Use a Trie to quickly check if a substring of target, starting at a given index, is a valid prefix.
  • Utilize dynamic programming (DP) where dp[i] represents the minimum number of valid prefixes used to form the target substring target[0:i].
  • For each position i where dp[i] is valid, traverse the Trie following target[i:] to update future positions in dp.
  • The approach avoids exploring unnecessary substrings by breaking early when the match in the Trie fails.

Space and Time Complexity

Time Complexity: O(n * m) in the worst-case where n is the length of target and m is the maximum length of a word (or the average length of matching prefixes). Building the Trie takes O(total_characters_in_words) which is ≤ 10^5. Space Complexity: O(total_characters_in_words) for the Trie plus O(n) for the dp array.

Solution

We first build a Trie from the words array. This Trie allows us to check any prefix efficiently since every node in the Trie stands for a valid prefix. We then use dynamic programming where dp[i] is the minimum number of valid strings needed to form the prefix target[0:i]. Starting from dp[0] = 0, for every index i we traverse the Trie following target[i:] until the path is no longer valid; for each valid traverse ending at index j (meaning target[i:j+1] is a valid prefix), we update dp[j+1] to be the minimum of its current value and dp[i] + 1. Finally, if dp[target.length] remains infinity (or a very large number), we return -1, otherwise we return that value.

Code Solutions

# Python solution with line-by-line comments
class TrieNode:
    def __init__(self):
        self.children = {}  # dictionary to store children nodes

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        # Insert each character, creating new nodes as necessary
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]

def min_valid_strings(words, target):
    # Build the Trie from words
    trie = Trie()
    for word in words:
        node = trie.root
        for char in word:
            # Insert prefix up to each character (every node is valid)
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
    
    n = len(target)
    # Initialize dp array: dp[i] is the min count to form target[0:i]
    dp = [float("inf")] * (n + 1)
    dp[0] = 0  # base case; empty string requires 0 valid prefixes

    # Iterate through each possible starting position
    for i in range(n):
        if dp[i] == float("inf"):
            continue
        node = trie.root  # reset the trie pointer at each new starting index
        # Try to extend the substring starting from i
        j = i
        while j < n and target[j] in node.children:
            node = node.children[target[j]]
            # target[i:j+1] is a valid prefix since it exists in the Trie
            dp[j + 1] = min(dp[j + 1], dp[i] + 1)
            j += 1
    # Return the result: if dp[n] is infinity, target can't be formed.
    return dp[n] if dp[n] != float("inf") else -1

# Example usage:
words = ["abc", "aaaaa", "bcdef"]
target = "aabcdabc"
print(min_valid_strings(words, target))  # Output: 3
← Back to All Questions