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 II

Difficulty: Hard

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 defined as a prefix of any string in the words array.
  • The problem can be viewed as a prefix matching problem where we need to find how many prefixes are needed to completely form the target string.
  • A greedy approach can be utilized to find the longest valid prefixes first, minimizing the count of valid strings used.
  • If at any point a character in target cannot match with any prefix in words, we should return -1.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of the target string and m is the number of strings in the words array.
Space Complexity: O(w), where w is the total length of all strings in the words array for storing the prefixes.

Solution

To solve this problem, we can use a greedy algorithm. We will iterate through the target string while trying to match the longest prefix from the words array. For each position in the target, we will check all possible prefixes from the words and see if they can match the current substring of target. We will keep track of the number of valid prefixes used and return the count once the entire target is matched.

  1. Create a set of valid prefixes from the words.
  2. Initialize a counter for the number of valid strings.
  3. Traverse through the target, and at each step, attempt to match the longest valid prefix from the set.
  4. If a match is found, increment the counter and move forward in the target.
  5. If no valid prefix can be matched at any point, return -1.

Code Solutions

def minValidStrings(words, target):
    valid_prefixes = set()
    
    # Collect all valid prefixes
    for word in words:
        for i in range(1, len(word) + 1):
            valid_prefixes.add(word[:i])
    
    count = 0
    i = 0
    while i < len(target):
        found = False
        for j in range(len(target), i, -1):
            if target[i:j] in valid_prefixes:
                count += 1
                i = j
                found = True
                break
        if not found:
            return -1
    
    return count
← Back to All Questions