leetcode

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

2707.cpp (546B)

      1 class Solution {
      2   public:
      3     int minExtraChar(const string &s, const vector<string> &dictionary) {
      4         unordered_set<string> us(begin(dictionary), end(dictionary));
      5         int dp[51] = {0};
      6 
      7         for (int i = s.size() - 1; i >= 0; i--) {
      8             int mini = s.size();
      9             for (int j = i; j < s.size(); j++) {
     10                 int crnt = us.count(s.substr(i, j - i + 1)) ? 0 : j - i + 1;
     11                 mini = min(mini, dp[j + 1] + crnt);
     12             }
     13             dp[i] = mini;
     14         }
     15 
     16         return *begin(dp);
     17     }
     18 };