Today I have done leetcode's September LeetCoding Challenge with cpp.

September LeetCoding Challenge 23

Description

Extra Characters in a String

You are given a 0-indexed string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings.

Return the minimum number of extra characters left over if you break up s optimally.

Example 1:

Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
Output: 1
Explanation: We can break s in two substrings: "leet" from index 0 to 3 and "code" from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.

Example 2:

Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
Explanation: We can break s in two substrings: "hello" from index 3 to 7 and "world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.

Constraints:

• 1 <= s.length <= 50
• 1 <= dictionary.length <= 50
• 1 <= dictionary[i].length <= 50
• dictionary[i] and s consists of only lowercase English letters
• dictionary contains distinct words

Solution

struct TrieNode {
  bool end = false;
  TrieNode *child[26] = {};
};
void insert(TrieNode *root, const string &word) {
  TrieNode *cur = root;
  for(auto c : word) {
    if(!cur->child[c - 'a']) cur->child[c - 'a'] = new TrieNode();
    cur = cur->child[c - 'a'];
  }
  cur->end = true;
}
class Solution {
  TrieNode *root = new TrieNode();
  int solve(const string &s, int position, vector<int> &memo) {
    if(position == s.length()) return 0;
    if(memo[position] != -1) return memo[position];
    int initPositon = position;
    int result = 1 + solve(s, position + 1, memo);
    TrieNode *current = root;
    while(position < s.length() && current->child[s[position] - 'a']) {
      current = current->child[s[position] - 'a'];
      position += 1;
      if(current->end) {
        result = min(result, solve(s, position, memo));
      }
    }
    return memo[initPositon] = result;
  }
public:
  int minExtraChar(string s, vector<string>& dictionary) {
    vector<int> memo(s.length(), -1);
    for(auto &word : dictionary) {
      insert(root, word);
    }
    return solve(s, 0, memo);
  }
};