Practice/Meta/Leetcode 3291. Minimum Number of Valid Strings to Form Target I

Leetcode 3291. Minimum Number of Valid Strings to Form Target I

CodingMust

Problem

You are given an array of strings called words and a single string target. Your task is to determine the minimum number of prefix segments needed to construct the target string.

A valid segment is defined as any prefix of any word in the words array. A prefix of a string is any substring that starts from the beginning of that string (including the string itself).

You must concatenate these valid segments in order to form the target string exactly. Return the minimum number of such segments required, or -1 if it's impossible to form the target.

Requirements

1. Only prefixes of words from the input array can be used as segments
2. Segments must be concatenated in the exact order to match the target
3. Each segment can be any length from 1 character up to the full length of a word
4. The same word can contribute multiple different prefixes
5. Return the minimum count of segments, or -1 if the target cannot be formed

Constraints

• 1 ≤ words.length ≤ 100
• 1 ≤ words[i].length ≤ 5000
• 1 ≤ target.length ≤ 5000
• The total length of all words combined will not exceed 100,000
• All strings consist of lowercase English letters only
• Time complexity expectation: O(n × m) where n is target length and m is total characters in words
• Space complexity expectation: O(n + total word characters)

Examples

Example 1:

Input: words = ["abc", "ab", "bc", "def"], target = "abcdef" Output: 2 Explanation: We can use prefix "abc" (from "abc") and prefix "def" (from "def") to form "abcdef".

Example 2:

Input: words = ["hello", "world"], target = "bye" Output: -1 Explanation: No prefix from the given words can match the start of "bye".

Example 3:

Input: words = ["a", "b", "c"], target = "abc" Output: 3 Explanation: We need three segments: "a", "b", and "c".

Example 4:

Input: words = ["ab", "abc", "abcd"], target = "abcd" Output: 1 Explanation: The entire target matches the prefix "abcd" from the word "abcd".