Alternative solution with hashing and seg tree beats 95% + approach
Intuition\nLet dp[i] represent the result for the prefix of length i in the target word. We will hash all possible prefixes that can be used from the vector wor
# Intuition\nLet dp[i] represent the result for the prefix of length i in the target word. We will hash all possible prefixes that can be used from the vector words.\n\n# Approach\nIn the segment tree, let\'s store the minimum result we can achieve for a given prefix. If we reach that prefix during the loop, we will binary search the maximum length by which we can extend from index i and update the results in the segment tree accordingly\n\n# Complexity\nw=words.length()\nz=words[i].length();\n- Time complexity:\nO(n*logn+w*z)\n\n- Space complexity:\no(n+w*z)\n\n# Code\n```cpp []\ntypedef long long ll;\nconst int MOD1 = 1e9 + 7;\nconst int MOD2 = 1e9 + 9;\nconst int st1 = 139;\nconst int st2 = 137;\nconst int N = 5e4 + 5;\nbool calc=false;\nll pot1[N], pot2[N], h1[N], h2[N];\n//segment tree start\nint d[N*4], push[N*4];\nvoid add(int x, int var){\n    if(d[x]>var) d[x]=var;\n    if(!push[x]||push[x]>var) push[x]=var;\n}\nvoid pushuj(int x){\n    if(!push[x]) return;\n    add(x*2, push[x]);\n    add(x*2+1, push[x]);\n    push[x]=0;\n}\nvoid build(int x, int l, int r){\n    if(l==r){\n        if(l==1) d[x]=0;\n        else d[x]=1e9;\n        return;\n    }\n    pushuj(x);\n    int sr=(l+r)/2;\n    build(x*2, l, sr);\n    build(x*2+1, sr+1, r);\n    d[x]=min(d[x*2], d[x*2+1]);\n}\nvoid update(int x, int l, int r, int a, int b, int var){\n    if(a<=l&&r<=b){\n        add(x, var);\n        return;\n    }\n    pushuj(x);\n    int sr=(l+r)/2;\n    if(a<=sr) update(x*2, l, sr, a, b, var);\n    if(sr<b) update(x*2+1, sr+1, r, a, b, var);\n    d[x]=min(d[x*2], d[x*2+1]);\n}\nint query(int x, int l, int r, int a, int b){\n    if(a<=l&&r<=b){\n        return d[x];\n    }\n    pushuj(x);\n    int res=1e9;\n    int sr=(l+r)/2;\n    if(a<=sr) res=min(res, query(x*2, l, sr, a, b));\n    if(sr<b) res=min(res, query(x*2+1, sr+1, r, a, b));\n    d[x]=min(d[x*2], d[x*2+1]);\n    return res;\n}\n//segment tree end\nvoid pre(){\n    calc=true;\n    pot1[0]=pot2[0]=1;\n    for(int i=1;i<N;i++){\n        pot1[i]=(pot1[i-1]*st1)%MOD1;\n        pot2[i]=(pot2[i-1]*st2)%MOD2;\n    }\n}\npair<int, int> get(int a, int b) { //get hash from target\n    ll hash1 = (h1[a] - (h1[b+1] * pot1[b-a+1]) % MOD1 + MOD1) % MOD1;\n    ll hash2 = (h2[a] - (h2[b+1] * pot2[b-a+1]) % MOD2 + MOD2) % MOD2;\n    return {hash1, hash2};\n}\nstruct pair_hash { //hash function for unordered_set\n    template <class T1, class T2>\n    std::size_t operator() (const std::pair<T1, T2>& pair) const {\n        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);\n    }\n};\nclass Solution {\npublic:\n    int minValidStrings(vector<string>& words, string target) {\n        unordered_set<pair<int, int>, pair_hash> zb;\n        if(!calc) pre();\n        for(auto &s : words){//hashing all prefixes\n            int m=s.size();\n            ll hash1=0, hash2=0;\n            for(int i=0;i<m;i++){\n                hash1=(hash1+pot1[i]*s[i])%MOD1;\n                hash2=(hash2+pot2[i]*s[i])%MOD2;\n                zb.insert({hash1, hash2});\n            }\n        }\n        target=".."+target;\n        int n=target.size(), rozm=1;\n        while(rozm<n){\n            rozm<<=1;\n        }\n        build(1, 1, rozm);\n        vector<int> dp(n+1, 1e9);\n        dp[1]=0;\n        h1[n+1]=h2[n+1]=h1[0]=h2[0]=0;\n        for(int i=n;i>=1;i--){//hash target\n            h1[i]=(h1[i+1]*st1+target[i])%MOD1;\n            h2[i]=(h2[i+1]*st2+target[i])%MOD2;\n        }\n        for(int i=1;i<n-1;i++){\n            dp[i]=query(1, 1, rozm, i, i);\n            if(dp[i]==1e9) continue;\n            int l=i+1, r=n-1, res=0;\n            while(l<=r){//get maximum length\n                int sr=(l+r)/2;\n                if(zb.find(get(i+1, sr))!=zb.end()){\n                    res=max(res, sr);\n                    l=sr+1;\n                }\n                else r=sr-1;\n            }\n            if(!res) continue;\n            update(1, 1, rozm, i+1, res, dp[i]+1);\n        }\n        dp[n-1]=query(1, 1, rozm, n-1, n-1);\n        return (dp[n-1]==1e9) ? -1 : dp[n-1];\n    }\n};\n```
['C++']