leetcode

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 };