easy solutions | z-algorithm | c++ | greedy
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nuse z-algothm to calcul
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nuse z-algothm to calculate the longest substring of target that begins at position k and is a prefix of any word in words and it is stored in array match then use greedy algorithm to calculate minimum steps\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minValidStrings(vector<string>& words, string target) {\n        int n = target.size();\n        vector<int> match(n, 0);\n        for (auto& word : words) {\n            string s = word + "#" + target;\n            int excess = word.size() + 1;\n            int nn = s.size();\n            // z-algorithm\n            vector<int> z(nn);\n            int x = 0, y = 0;\n            for (int i = 1; i < nn; i++) {\n                z[i] = max(0, min(z[i - x], y - i + 1));\n                while (i + z[i] < nn && s[z[i]] == s[i + z[i]]) {\n                    x = i;\n                    y = i + z[i];\n                    z[i]++;\n                }\n                if (i >= excess && z[i] > 0)\n                    match[i - excess] = max(match[i - excess], z[i]);\n            }\n        }\n        // greedy algorithm\n        int steps =0,currend=0,farthest=0;\n        for(int i=0; i<n; i++){\n            farthest = max(farthest, i+match[i]);\n            if(i==currend){\n                steps++;\n                currend =farthest;\n                if(currend>=n)  break;\n            }\n        }\n        // if we can\'t form the target\n        if(currend<n)   return -1;\n        return steps;\n    }\n};\n```
['Greedy', 'C++']