KMP + DP
Compute the KMP suffix length as prefix for the concatenation: (word + "#" + target) and check for target\'s suffixes which is the length of prefix.\nFor KMP ex
Compute the KMP suffix length as prefix for the concatenation: (word + "#" + target) and check for target\'s suffixes which is the length of prefix.\nFor KMP explanation refer to Tushar Roy\'s video: [https://www.youtube.com/watch?v=GTJr8OvyEVQ](https://www.youtube.com/watch?v=GTJr8OvyEVQ)\n$$dp[i]$$ represents the minimum number of \'good\' strings up to position \uD835\uDC56\n$$dp[i] = dp[i - l] + 1$$, where \uD835\uDC59 is the length of the word\'s prefix that matches the target\'s suffix ending at position \uD835\uDC56.\n\n\uD83D\uDCAA\uD83D\uDE80Keep leetcoding! Keep improving!\n# Code\n```csharp []\npublic class Solution {\n    public int MinValidStrings(string[] words, string target) \n    {\n        int nt = target.Length;\n        int[] dp = new int[nt + 1];\n        HashSet<int>[] preLengths = new HashSet<int>[nt + 1];\n        for (int i = 0; i <= nt; i++) \n        {\n            dp[i] = nt + 1;\n            preLengths[i] = new HashSet<int>();\n        }\n\n        dp[0] = 0;\n        foreach(var word in words) \n        {\n            StringBuilder sb = new StringBuilder(word);\n            sb.Append("#");\n            sb.Append(target);\n            var lpsConcat = CalculateSuffixAsPrefixKMP(sb.ToString());       \n            for (int i = 0; i < nt; i++) \n            {               \n                int posInConcat = word.Length + i + 1;  \n                if (lpsConcat[posInConcat] > 0) \n                {                   \n                    preLengths[i].Add(lpsConcat[posInConcat]);\n                }                   \n            }\n        }\n        \n        for (int i = 0; i < nt; i++) \n        {\n            foreach(var len in preLengths[i]) \n            {\n                dp[i + 1] = Math.Min(dp[i + 1 - len] + 1, dp[i+1]);\n            }\n        }\n        \n        return dp[nt] > nt ? -1 : dp[nt];\n    }\n\n    public int[] CalculateSuffixAsPrefixKMP(string s) \n    {\n        int n = s.Length;\n        int[] lps = new int[n];\n        lps[0] = 0;\n        for (int i = 1; i < n; i++) \n        {\n           int t = lps[i-1];\n           \n            while (t > 0 && s[i] != s[t])\n                t = lps[t-1];\n            if (s[i] == s[t])\n                t++;\n            lps[i] = t;\n        }\n        return lps;\n    }\n}\npublic class DescendingComparer : IComparer<int>\n{\n    public int Compare(int x, int y)\n    {\n        return y.CompareTo(x);\n    }\n}\n```
['C#']