Minimum Number of Valid Strings to Form Target I

This approach uses dynamic programming combined with a hash set. We pre-compute all valid prefixes from the words array and store them in a hash set for fast lookups. Then, we use a DP array dp[i] to store the minimum number of strings to form the first i characters of the target. The DP state is updated by checking all possible last valid strings ending at each position.

• Create a HashSet<String> to store all valid prefixes.
• Iterate through each word in words, generate all its prefixes, and add them to the hash set.
• Initialize a DP array dp of size target.length() + 1 with a large value, and set dp[0] = 0.
• Use nested loops to iterate through all substrings target.substring(j, i).
• If dp[j] is reachable and target.substring(j, i) is in the hash set, update dp[i] with min(dp[i], dp[j] + 1).
• The final answer is dp[target.length()], or -1 if it's still the large value.

The core of this method is the dynamic programming recurrence: dp[i] = min(dp[j] + 1) over all j < i such that target.substring(j, i) is a valid prefix. To make the check for a valid prefix efficient, we first populate a HashSet with all prefixes of every word in the input words. This pre-computation step allows us to check if any given substring is a valid prefix in approximately constant time on average (though proportional to the substring's length due to hashing).

The main DP loop then iterates through all possible end-points i of a prefix of target, and for each i, it tries all possible start-points j. If target.substring(j, i) is found in our pre-computed set, we have a potential way to form target.substring(0, i), and we update dp[i] accordingly.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minStrings(String[] words, String target) {
        Set<String> validPrefixes = new HashSet<>();
        for (String word : words) {
            for (int k = 1; k <= word.length(); k++) {
                validPrefixes.add(word.substring(0, k));
            }
        }

        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 (int j = 0; j < i; j++) {
                if (dp[j] != Integer.MAX_VALUE) {
                    String sub = target.substring(j, i);
                    if (validPrefixes.contains(sub)) {
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                }
            }
        }

        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }
}