LeetCode 3291: Minimum Number of Valid Strings to Form Target I

Explanation:

To solve this problem, we can iterate through the target string and keep track of the prefixes of words that can form the current substring of the target. We can use dynamic programming to efficiently compute the minimum number of valid strings needed to form the target string.

1. Initialize a DP array of size equal to the length of the target string + 1. DP[i] will store the minimum number of valid strings required to form a target substring of length i.
2. Initialize DP[0] = 0, as an empty substring requires 0 valid strings.
3. Iterate through the target string character by character:
   • For each character in the target string, try to match the prefixes of words with the current substring of the target.
   • If a prefix matches the current substring, update DP[i] with the minimum of (DP[i], DP[i - prefix.length] + 1) where prefix.length is the length of the matched prefix.
4. Finally, return DP[target.length()] if it is not equal to Integer.MAX_VALUE, else return -1. :

class Solution {
    public int minNumOfValidStrings(String[] words, String target) {
        int n = target.length();
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (String word : words) {
                if (word.length() <= i && target.substring(i - word.length(), i).equals(word)) {
                    dp[i] = Math.min(dp[i], dp[i - word.length()] + 1);
                }
            }
        }
        
        return dp[n] != Integer.MAX_VALUE ? dp[n] : -1;
    }
}