leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

3291.cpp (1297B)

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