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 I

Number: 3559

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array of strings (words) and a target string, determine the minimum number of valid strings that can be concatenated to form the target. A valid string is defined as any prefix of any string in words. If it is not possible to form the target, return -1.

Key Insights

  • A valid chunk is any prefix of any given word, hence we can represent all these prefixes efficiently using a Trie.
  • Dynamic Programming (DP) can be used where dp[i] represents the minimum pieces required to form target[i:].
  • By traversing the target string while simultaneously traversing the Trie, we can quickly check which substrings (starting from the current position) are valid.
  • The problem can be broken down into subproblems where if target[i:j] is valid then the answer can be obtained as 1 + dp[j].

Space and Time Complexity

Time Complexity: O(n * L) where n is the length of the target and L is the average length of the valid prefix paths (bounded by the length of words but overall sum of words' lengths is limited). Space Complexity: O(total characters in words) for the Trie + O(n) for the DP array.

Solution

We first build a Trie containing all valid prefixes from the input words. During the DP phase, for each index i in target, we traverse the Trie following characters from target[i:] and update dp[i] with the minimum count found (1 + dp[j] where j is the position reached at the end of a valid prefix). If no valid prefix is found starting from index i, then dp[i] remains infinite and eventually we return -1 if forming the target is impossible.

Code Solutions

# Python solution with detailed comments
def min_prefix_concat(words, target):
    # Build a Trie from the input words. Every prefix encountered is valid.
    trie = {}
    for word in words:
        current = trie
        # Iterate over each character in the word.
        for char in word:
            # If a sub-dictionary doesn't exist for the char, create one.
            if char not in current:
                current[char] = {}
            current = current[char]
    
    n = len(target)
    # dp[i] will hold the minimum number of valid strings needed to form target[i:].
    dp = [float('inf')] * (n + 1)
    dp[n] = 0  # Base case: no pieces needed for an empty substring.
    
    # Process dp from the end of target to the beginning.
    for i in range(n - 1, -1, -1):
        current = trie
        # Try to extend the substring starting at i.
        for j in range(i, n):
            char = target[j]
            # If the current prefix doesn't exist in the Trie, break.
            if char not in current:
                break
            current = current[char]
            # We have a valid prefix from i to j.
            if dp[j + 1] != float('inf'):
                dp[i] = min(dp[i], 1 + dp[j + 1])
    
    return dp[0] if dp[0] != float('inf') else -1

# Example usage:
#print(min_prefix_concat(["abc","aaaaa","bcdef"], "aabcdabc"))  # Expected output: 3
← Back to All Questions