Z-Function boils to Min Jumps II Easy Short Fast | Comments | C++
Complexity\nn = words.length(), t = target.length(), K = len of each words\n- Time complexity: O(n * (K+t))\n\n- Space complexity: O(n)\n##### This solution is 
# Complexity\n`n = words.length(), t = target.length(), K = len of each words`\n- Time complexity: $$O(n * (K+t))$$\n\n- Space complexity: $$O(n)$$\n##### This solution is very close to the optimal solution and very fast considering the small size of the code for this solution.\n![image.png](https://assets.leetcode.com/users/images/b3010c5f-a9cc-4fbf-a3c1-f920ff32a218_1726377685.815441.png)\n*Only with fast-IO and no other optimizations to the below code. Some inlining and unnecessary if-statements may improve the time.\n# Code\nThere is also the clean C++ code thats very short with no comments (relative to other sols).\n\n\n```cpp []\n#include <bits/stdc++.h>\nusing namespace std;\nvector<int> z_function(string s) {\n    // Source: https://cp-algorithms.com/string/z-function.html\n    int n = s.size();\n    vector<int> z(n);\n    int l = 0, r = 0;\n    for(int i = 1; i < n; i++) {\n        if(i < r) {\n            z[i] = min(r - i, 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] > r) {\n            l = i;\n            r = i + z[i];\n        }\n    }\n    return z;\n}\nclass Solution {\n\npublic:\n    //Solution for https://leetcode.com/problems/jump-game-ii/description/\n    int jump(vector<int>& nums) {\n        int size = (int) nums.size();\n        if(size == 1) return 0;\n        vector<long long> minJumps(size, INT_MAX); // minJumps[i] is the min num of jumps to get to nums[i]\n        minJumps[0] = 0;\n        for(int i = 0; i < size; i++) {\n            // No check for minJumps[i] == INT_MAX because the test cases are generated such that you can reach nums[n-1]\n            for(int j = min(i + nums[i], size - 1); j > i; j--) {\n                if(minJumps[j] <= minJumps[i] + 1) {\n                    break; // because then everything below is ALSO better/equal to this current permutation\n                }else minJumps[j] = minJumps[i] + 1;\n            }\n        }\n        return minJumps[size - 1];\n    }\n    int minValidStrings(vector<string>& words, string target) {\n        int n = words.size();\n        vector<int> match(target.size(), 0);\n        // match[i] will be the longest match starting at index i using Any word.\n        // So for example with target = "abcde", and words = ["bcd"]\n        // match = {0, 3, 0, 0, 0}\n        for(string& word : words) {\n            string comb = word + "!" + target;\n            vector<int> z = z_function(comb); // We use the z function\n            // Definition of Z[i]:\n            // (from cp-algorithms)\n            // z[i] = the length of the longest string that is, at the same time, a prefix of $s$\u200A\n            // and a prefix of the suffix of `s` starting at `i`.\n            for(int i = 0; i < target.size(); i++) {\n                // z[n + j + 1]\n                // we notice comb[n+i+1] = target[i], because n is word.length and 1 for the separator \'!\'\n                // that means z[n+i+1] = longest string that matches\n                // : words[0...X-1] [prefix of comb]\n                // : target[j...j+(X-1)] (which is target starting from index j) [suffix of comb]\n                // X is the possible values, then Z[n+i+1] = max(all X that matches)\n                // in other words, it is the longest string that can be matched\n                // using this word at index j\n\n                // Example: target = "abacda", word = "acb"\n                // match {0, 0, 0, 0, 0, 0} ->\n                // {\n                //   1 [match \'a\'],\n                //   0 [no match],\n                //   2 [match \'ac\'],\n                //   0 [no match],\n                //   0 [no match],\n                //   1 [match \'a\']\n                // }\n                match[i] = max(match[i], z[word.length() + i + 1]);\n            }\n        }\n        // match[i] will be the longest length we can match from i\n        // In other words, we can jump either from j= 0 --> match[i]\n        // to match[i+j] using one operation/string\n\n        match.push_back(0); // We add extra \'0\' for the end result (where everything is concatenated).\n        int ans = jump(match);\n        return ans >= INT_MAX ? -1 : ans;\n    }\n};\n```\n```cpp [Clean C++]\n#include <bits/stdc++.h>\nusing namespace std;\nvector<int> z_function(string s) {\n    int n = s.size();\n    vector<int> z(n);\n    int l = 0, r = 0;\n    for(int i = 1; i < n; i++) {\n        if(i < r) {\n            z[i] = min(r - i, 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] > r) {\n            l = i;\n            r = i + z[i];\n        }\n    }\n    return z;\n}\nclass Solution {\npublic:\n    int jump(vector<int>& nums) {\n        int size = (int) nums.size();\n        if(size == 1) return 0;\n        vector<long long> minJumps(size, INT_MAX);\n        minJumps[0] = 0;\n        for(int i = 0; i < size; i++) {\n            for(int j = min(i + nums[i], size - 1); j > i; j--) {\n                if(minJumps[j] <= minJumps[i] + 1) {\n                    break;\n                }else minJumps[j] = minJumps[i] + 1;\n            }\n        }\n        return minJumps[size - 1];\n    }\n    int minValidStrings(vector<string>& words, string target) {\n        int n = words.size();\n        vector<int> match(target.size(), 0);\n        for(string& word : words) {\n            string comb = word + "!" + target;\n            vector<int> z = z_function(comb);\n            for(int i = 0; i < target.size(); i++) {\n                match[i] = max(match[i], z[word.length() + i + 1]);\n            }\n        }\n        match.push_back(0);\n        int ans = jump(match);\n        return ans >= INT_MAX ? -1 : ans;\n    }\n};\n```
['String', 'Dynamic Programming', 'String Matching', 'C++']