non-dp solution, ~20 lines, 76 ms, 11.72 MB
Complexity\nLet w = length of longest word, k = number of words, m = total length of words, n = length of target.\n- Time complexity: O(m + n * k)\n- Space comp
# Complexity\nLet w = length of longest word, k = number of words, m = total length of words, n = length of target.\n- Time complexity: O(m + n * k)\n- Space complexity: O(w + n)\n\nNote that n * k and m are both ~5,000,000. If n * k were much bigger than m, then the following solution would be better: https://leetcode.com/problems/minimum-number-of-valid-strings-to-form-target-ii/solutions/5789605/c-simplest-and-shortest-solution-two-pointer-and-rolling-hash-only-no-trees-tries-kmp-z-etc/\n\n# Code\n```c []\nint minValidStrings(char** words, int wordsSize, char* target) {\n    int lenLongestWord = 0, len = strlen(target), steps = 0;\n    for (int i = 0; i < wordsSize; i++) {\n        int lenWord = strlen(words[i]);\n        if (lenWord > lenLongestWord) lenLongestWord = lenWord;\n    }\n    int kmp[lenLongestWord + 1], best[len];\n    memset(best, 0, len * sizeof(int));\n\n    for (int i = 0; i < wordsSize; i++) { // KMP\n        const char *word = words[i];\n        kmp[0] = 0;\n        for (int j = 0, k = 1; word[k];) {\n            if (word[k] == word[j]) kmp[k++] = j++ + 1;\n            else if (j) j = kmp[j - 1];\n            else kmp[k++] = 0;\n        }\n        for (int j = 0, k = 0; target[k];) {\n            if (target[k] == word[j]) {\n                best[k] = best[k] > j + 1 ? best[k] : j + 1;\n                k++; j++;\n            } else if (j) j = kmp[j - 1];\n            else k++;\n        }\n    }\n\n    for (int remaining = len; remaining; steps++) { // greedy\n        if (!best[remaining - 1]) return -1;\n        remaining -= best[remaining - 1];\n    }\n    return steps;\n}\n```
['Greedy', 'C', 'String Matching']