leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

3291.cpp (1297B)

0 class Trie { 1 struct Node { 2 Node *children[26] = {0}; 3 } root; 4 5 public: 6 void insert(const string &s) { 7 Node *crnt = &root; 8 9 for (const char c : s) { 10 const int idx = c - 'a'; 11 if (!crnt->children[idx]) crnt->children[idx] = new Node(); 12 crnt = crnt->children[idx]; 13 } 14 } 15 16 int find(const string &s, int start) const { 17 const Node *crnt = &root; 18 int n = 0; 19 20 for (int i = start; i < size(s); i++, n++) { 21 const int idx = s[i] - 'a'; 22 if (!crnt->children[idx]) break; 23 crnt = crnt->children[idx]; 24 } 25 26 return n; 27 } 28 }; 29 30 class Solution { 31 public: 32 int minValidStrings(const vector<string> &words, const string &target) const { 33 static unsigned dp[5001]; 34 const int n = size(target); 35 Trie trie; 36 37 for (const auto &word : words) 38 trie.insert(word); 39 40 memset(dp, 0xFF, sizeof(dp)); 41 dp[0] = 0; 42 43 for (int i = 0; i < n; i++) { 44 if (dp[i] == -1) continue; 45 const int limit = trie.find(target, i); 46 for (int len = 1; len <= limit; len++) { 47 dp[i + len] = min(dp[i + len], dp[i] + 1); 48 } 49 } 50 51 return dp[n]; 52 } 53 };