DP + Z-Function + Segment Tree
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n- n = len(target)\nO(len(words) * n + sum(words[i]) + n * logn)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nusing ll = long long;\n\nstruct Node {\n    ll min;\n    \n    Node() {\n        min =0;\n    }\n};\n\nclass SegmentTree {\npublic:\n    vector<Node> segTree;\n\n    SegmentTree(vector<ll> &arr) {\n        ll n = arr.size();\n        segTree.resize(4 * n + 1);\n        build(0, 0, n - 1, arr);\n    }\n\n    void build(ll ind, ll low, ll high, vector<ll> &arr) {\n        if (low == high) {\n            segTree[ind].min = arr[low];\n            return;\n        }\n        ll mid = low + (high - low) / 2;\n        build(2 * ind + 1, low, mid, arr);\n        build(2 * ind + 2, mid + 1, high, arr);\n        segTree[ind].min = min(segTree[2 * ind + 1].min , segTree[2 * ind + 2].min);\n    }\n\n    void update(ll ind, ll low, ll high, ll i, ll val) {\n        if (low == high) {\n            segTree[ind].min = val;\n            return;\n        }\n        ll mid = (low + high) >> 1;\n        if (i <= mid) {\n            update(2 * ind + 1, low, mid, i, val);\n        }\n        else {\n            update(2 * ind + 2, mid + 1, high, i, val);\n        }\n        segTree[ind].min = min(segTree[2 * ind + 1].min , segTree[2 * ind + 2].min);\n    }\n\n    ll query(ll ind, ll low, ll high, ll l, ll r) {\n        if (low > r || high < l || low > high) return 1e9;\n\n        if (low >= l && high <= r) return segTree[ind].min;\n\n        ll mid = (low + high) >> 1;\n        ll left = query(2 * ind + 1, low, mid, l, r);\n        ll right = query(2 * ind + 2, mid + 1, high, l, r);\n        return min(left, right);\n    }\n};\n\n\nclass Solution {\nprivate:\n    vector<ll> z_function(string s) {\n        ll n = s.size();\n        vector<ll> z(n);\n        ll l = 0, r = 0;\n        for(ll 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    }\n    ll dfs(ll i, vector<ll> &match) {\n        if(i>=match.size()) return 0;\n        ll n = match.size();\n        ll m = match[i];\n        ll res=1e9;\n        for(ll j=1;j<=m;j++) res=min(res,1+dfs(i+j,match));\n        return res;\n    }\npublic:\n    int minValidStrings(vector<string>& words, string target) {\n        ll m = words.size();\n        ll n = target.size();\n        vector <ll> match(n);\n        for(ll i=0;i<m;i++) {\n            string s = words[i] + "#" + target;\n            vector <ll> z = z_function(s);\n            vector <ll> t;\n            for(ll j=words[i].size()+1;j<s.size();j++) {\n                t.push_back(z[j]);\n            }\n            for(ll k=0;k<t.size();k++) {\n                match[k]=max(match[k],t[k]);\n            }\n        }\n        vector <ll> dp(n,1e9);\n        SegmentTree sgt(dp);\n        for(ll i=n-1;i>=0;i--) {\n            ll m = match[i];\n            if(m==0) continue;\n            ll q = sgt.query(0, 0, n-1, min(i+1,n-1),min(i+m,n-1));\n            if(q==1e9) {\n                if(i+m>=n) {\n                    dp[i]=1;\n                    sgt.update(0,0,n-1,i,1);\n                } \n            }\n            else {\n                if(i+m>=n) {\n                    dp[i]=1;\n                    sgt.update(0,0,n-1,i,1);\n                }\n                else {\n                    dp[i]=1+q;\n                    sgt.update(0,0,n-1,i,1+q);\n                }\n            }\n        }\n        return dp[0]==1e9?-1:dp[0];\n    }\n};\n```
['Dynamic Programming', 'Segment Tree', 'C++']