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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Valid Strings to Form Target I

Difficulty: Medium

Problem 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.

Key Insights

  • A valid string is a prefix of any word in the words array.
  • The problem can be approached by attempting to match segments of the target with valid prefixes from words.
  • A greedy approach or a dynamic programming approach can be utilized to minimize the number of valid strings needed to form target.
  • The solution may involve using a Trie data structure for efficient prefix matching.

Space and Time Complexity

Time Complexity: O(n * m) where n is the length of the target and m is the average length of the words, due to the need to check prefixes. Space Complexity: O(k) where k is the number of unique prefixes stored, which may be derived from the words.

Solution

To solve this problem, we can use a dynamic programming approach. We maintain a DP array where dp[i] represents the minimum number of valid strings needed to form the substring target[0:i]. We initialize dp[0] to 0 since no strings are needed to form an empty target.

We iterate through each position in target and for each position, we check all possible prefixes of strings in words that could end at that position. If a valid prefix is found, we update the DP array to reflect the minimum number of valid strings used.

The final result will be found in dp[target.length], and if it remains infinity (or a designated sentinel value), it indicates that it is not possible to form the target.

Code Solutions

def min_valid_strings(words, target):
    # Create a set of prefixes from words
    prefixes = set()
    for word in words:
        for i in range(1, len(word) + 1):
            prefixes.add(word[:i])
    
    # Initialize DP array to a large number
    dp = [float('inf')] * (len(target) + 1)
    dp[0] = 0  # Base case: zero strings needed to form empty target
    
    # Fill the DP array
    for i in range(1, len(target) + 1):
        for j in range(i):
            if target[j:i] in prefixes:
                dp[i] = min(dp[i], dp[j] + 1)
    
    return dp[len(target)] if dp[len(target)] != float('inf') else -1
← Back to All Questions