(Officially intended approach) Trie + Double Rolling Hash + Lazy Segment tree + Binary search + DP
Intuition\n# Approach\n\n- Idea is quite simple. For all prefix that exist in words, generate a hash value. (double hash)\n- Now DP[j] = min(DP[j],DP[i-1]+1) fo
# Intuition\n# Approach\n\n- Idea is quite simple. For all prefix that exist in words, generate a hash value. (double hash)\n- Now `DP[j] = min(DP[j],DP[i-1]+1)` for all j such that `targert[i:j]` is one of the prefix of given words.\n- We build a rolling hash to query hash of `targert[i:j]` in O(1)\n- Then we find longest string starting at index i, which is present in given words. Using binary search. \n- `update(DP[i], DP[j])` as minimum of `DP[i-1]+1` where j is longest prefix present in words. Using lazy segment tree\n\n\n# Complexity\n- Time complexity:\n`O(sum(words) + len(target)*log(target))`\n\n- Space complexity:\n`O(26*sum(words) + len(target))`\n\n# Code\n```cpp []\n#include <iostream>\n#include <vector>\n#include <string>\n#include <unordered_set>\n#include <unordered_map>\n#include <memory>\n#include <limits.h>\n#include <functional>\n\n#define ll long long\n\nusing namespace std;\n\n// Hash function for pair<int, int>\nstruct pair_hash {\n    template <class T1, class T2>\n    std::size_t operator()(const std::pair<T1, T2>& p) const {\n        auto h1 = std::hash<T1>{}(p.first);\n        auto h2 = std::hash<T2>{}(p.second);\n        return h1 ^ h2; // or use boost::hash_combine for better hash distribution\n    }\n};\n\nclass TrieNode {\npublic:\n    unordered_map<char, TrieNode*> children;\n    bool isEndOfWord;\n\n    TrieNode() : isEndOfWord(false) {}\n};\n\nclass Trie {\npublic:\n    TrieNode* root;\n    \n    Trie() {\n        root = new TrieNode();\n    }\n\n    ~Trie() {\n        deleteTrie(root);\n    }\n\n    void deleteTrie(TrieNode* node) {\n        if (node == nullptr) return;\n        for (auto& pair : node->children) {\n            deleteTrie(pair.second);\n        }\n        delete node;\n    }\n\n    void insert(const string& word) {\n        TrieNode* current = root;\n        for (char ch : word) {\n            if (current->children.find(ch) == current->children.end()) {\n                current->children[ch] = new TrieNode();\n            }\n            current = current->children[ch];\n        }\n        current->isEndOfWord = true;\n    }\n\n    void dfs(TrieNode* node, pair<int, int> hash, int base1, int base2, int mod1, int mod2, unordered_set<pair<int, int>, pair_hash>& hashSet) {\n        if (node == nullptr) return;\n        hashSet.insert(hash);\n\n        for (auto& pair : node->children) {\n            char ch = pair.first;\n            TrieNode* child = pair.second;\n            int newHash1 = ((ll)hash.first * base1 + (ch - \'a\' + 1)) % mod1;\n            int newHash2 = ((ll)hash.second * base2 + (ch - \'a\' + 1)) % mod2;\n            dfs(child, {newHash1, newHash2}, base1, base2, mod1, mod2, hashSet);\n        }\n    }\n\n    void generatePrefixHashes(int base1, int base2, int mod1, int mod2, unordered_set<pair<int, int>, pair_hash>& hashSet) {\n        dfs(root, {0, 0}, base1, base2, mod1, mod2, hashSet);\n    }\n};\n\nclass RollingHash {\npublic:\n    vector<pair<int, int>> hashArray;\n    vector<pair<int, int>> powerArray;\n    int base1, base2;\n    int mod1, mod2;\n    \n    RollingHash(const string& s, int base1, int base2, int mod1, int mod2) \n        : base1(base1), base2(base2), mod1(mod1), mod2(mod2) {\n        int n = s.size();\n        hashArray.resize(n + 1, {0, 0});\n        powerArray.resize(n + 1, {1, 1});\n\n        for (int i = 0; i < n; ++i) {\n            hashArray[i + 1].first = ((ll)hashArray[i].first * base1 + (s[i] - \'a\' + 1)) % mod1;\n            hashArray[i + 1].second = ((ll)hashArray[i].second * base2 + (s[i] - \'a\' + 1)) % mod2;\n            powerArray[i + 1].first = ((ll)powerArray[i].first * base1) % mod1;\n            powerArray[i + 1].second = ((ll)powerArray[i].second * base2) % mod2;\n        }\n    }\n\n    pair<int, int> getHash(int i, int j) {\n        int hash1 = ((ll)hashArray[j].first - ((ll)hashArray[i - 1].first * powerArray[j - i + 1].first) % mod1 + mod1) % mod1;\n        int hash2 = ((ll)hashArray[j].second - ((ll)hashArray[i - 1].second * powerArray[j - i + 1].second) % mod2 + mod2) % mod2;\n        return {hash1, hash2};\n    }\n};\n\nclass SegmentTree {\nprivate:\n    vector<int> tree;\n    vector<int> lazy;\n    int n;\n\n    void buildTree(const vector<int>& arr, int node, int start, int end) {\n        if (start == end) {\n            tree[node] = arr[start];\n        } else {\n            int mid = (start + end) / 2;\n            buildTree(arr, 2 * node + 1, start, mid);\n            buildTree(arr, 2 * node + 2, mid + 1, end);\n            tree[node] = min(tree[2 * node + 1], tree[2 * node + 2]);\n        }\n    }\n\n    void push(int node, int start, int end) {\n        if (lazy[node] != INT_MAX) {\n            tree[node] = min(tree[node], lazy[node]);\n            if (start != end) {\n                lazy[2 * node + 1] = min(lazy[2 * node + 1], lazy[node]);\n                lazy[2 * node + 2] = min(lazy[2 * node + 2], lazy[node]);\n            }\n            lazy[node] = INT_MAX;\n        }\n    }\n\n    void updateRange(int node, int start, int end, int l, int r, int value) {\n        push(node, start, end);\n        if (start > r || end < l) return;\n        if (start >= l && end <= r) {\n            tree[node] = min(tree[node], value);\n            if (start != end) {\n                lazy[2 * node + 1] = min(lazy[2 * node + 1], value);\n                lazy[2 * node + 2] = min(lazy[2 * node + 2], value);\n            }\n            return;\n        }\n        int mid = (start + end) / 2;\n        updateRange(2 * node + 1, start, mid, l, r, value);\n        updateRange(2 * node + 2, mid + 1, end, l, r, value);\n        tree[node] = min(tree[2 * node + 1], tree[2 * node + 2]);\n    }\n\n    int query(int node, int start, int end, int idx) {\n        push(node, start, end);\n        if (start == end) {\n            return tree[node];\n        }\n        int mid = (start + end) / 2;\n        if (idx <= mid) {\n            return query(2 * node + 1, start, mid, idx);\n        } else {\n            return query(2 * node + 2, mid + 1, end, idx);\n        }\n    }\n\npublic:\n    SegmentTree(const vector<int>& arr) {\n        n = arr.size();\n        tree.resize(4 * n);\n        lazy.resize(4 * n, INT_MAX);\n        buildTree(arr, 0, 0, n - 1);\n    }\n\n    void updateRange(int l, int r, int value) {\n        updateRange(0, 0, n - 1, l, r, value);\n    }\n\n    int query(int idx) {\n        return query(0, 0, n - 1, idx);\n    }\n};\n\nclass Solution {\npublic:\n    int minValidStrings(vector<string>& words, string target) {\n        unique_ptr<Trie> t = make_unique<Trie>();\n        for (const string& s : words) {\n            t->insert(s);\n        }\n        \n        unordered_set<pair<int, int>, pair_hash> hashSet;\n        int base1 = 31;\n        int base2 = 53;\n        int mod1 = 1000000007;\n        int mod2 = 1000000009;\n        t->generatePrefixHashes(base1, base2, mod1, mod2, hashSet);\n\n        RollingHash rh(target, base1, base2, mod1, mod2);\n        int n = target.size();\n        vector<int> dp(n + 1, n + 1);\n        dp[0] = 0;\n        SegmentTree st(dp);\n\n        for (int i = 0; i < n; ++i) {\n            int s = i - 1, e = n - 1;\n            while (s < e) {\n                int m = (s + e + 1) / 2;\n                auto [hash1, hash2] = rh.getHash(i + 1, m + 1);\n                if (hashSet.find({hash1, hash2}) != hashSet.end()) {\n                    s = m;\n                } else {\n                    e = m - 1;\n                }\n            }\n            if (s == i - 1) continue;\n            st.updateRange(i + 1, s + 1, st.query(i) + 1);\n        }\n        \n        int result = st.query(n);\n        return result == n + 1 ? -1 : result;\n    }\n};\n\n```
['C++']