leetcode

Solution to some Leetcode problems written in C++

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

2707.cpp (546B)

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