z-function + Jump game II
Approach\nLet\'s find for each index of target maximum prefix length in words. It\'s easy to do using z-function. Then it\'s exactly jump game II https://leetco
# Approach\nLet\'s find for each index of target maximum prefix length in words. It\'s easy to do using z-function. Then it\'s exactly jump game II https://leetcode.com/problems/jump-game-ii/description/\n\n```cpp []\n    vector<int> zFunction(string_view s) {\n        int n = size(s);\n        vector<int> z(n);\n        for (int i = 1, l = 0, r = 0; i < n; ++i) {\n            if (i <= r) {\n                z[i] = min(r - i + 1, z[i - l]);\n            }\n            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {\n                ++z[i];\n            }\n            if (i + z[i] - 1 > r) {\n                l = i, r = i + z[i] - 1;\n            }\n        }\n        return z;\n    }\n\n    int jump(vector<int>& nums) {\n        int ans = 0;\n        for (int l = 0, r = 0, n = size(nums); r < n; ++ans) {\n            int farthest = r;\n            for (int i = l; i <= r; ++i) {\n                farthest = max(farthest, nums[i] + i);\n            }\n            if (farthest == r) {\n                return -1;\n            }\n            l = r;\n            r = farthest;\n        }\n        return ans;\n    }\n\n    int minValidStrings(vector<string>& words, string t) {\n        const int n = size(t);\n        vector<int> prefixes(n);\n        for (const auto& w: words) {\n            const auto z = zFunction(w + \'#\' + t);\n            for (int i = size(w) + 1; i < size(z); ++i) {\n                prefixes[i - size(w) - 1] = max(prefixes[i - size(w) - 1], z[i]);\n            }\n        }\n        return jump(prefixes);\n    }\n```
['C++']