Sponsored
Sponsored
In this approach, we use dynamic programming to solve the problem. We define a DP array where dp[i] represents the minimum number of extra characters from index 0 to i of the string s. Initially, we set dp[0] to 0 because there are no extra characters in an empty prefix. For each index i while iterating through the string s, we check every j from 0 to i-1 and see if substring s[j:i] exists in the dictionary. If yes, we update dp[i] to min(dp[i], dp[j]), otherwise, we set dp[i] to dp[i-1] + 1.
Time Complexity: O(N^2*M), where N is the length of the string s and M is the average length of words in the dictionary.
Space Complexity: O(N) because of the DP array.
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4
5#define MAX_LENGTH 51
6
7bool isInDictionary(char *word, char dictionary[][MAX_LENGTH], int dictionarySize) {
8 for (int i = 0; i < dictionarySize; i++) {
9 if (strcmp(word, dictionary[i]) == 0) {
10 return true;
11 }
12 }
13 return false;
14}
15
16int minExtraChars(char *s, char dictionary[][MAX_LENGTH], int dictionarySize) {
17 int n = strlen(s);
18 int dp[n + 1];
19 for (int i = 0; i <= n; i++) {
20 dp[i] = i;
21 }
22 dp[0] = 0;
23 for (int i = 1; i <= n; i++) {
24 dp[i] = dp[i - 1] + 1;
25 for (int j = 0; j < i; j++) {
26 char sub[i - j + 1];
27 strncpy(sub, s + j, i - j);
28 sub[i - j] = '\0';
29 if (isInDictionary(sub, dictionary, dictionarySize)) {
30 if (dp[j] < dp[i]) {
31 dp[i] = dp[j];
32 }
33 }
34 }
35 }
36 return dp[n];
37}
38
39int main() {
40 char s[] = "leetscode";
41 char dictionary[][MAX_LENGTH] = {"leet", "code", "leetcode"};
42 int dictionarySize = 3;
43 int result = minExtraChars(s, dictionary, dictionarySize);
44 printf("%d\n", result); // Output: 1
45 return 0;
46}This C solution uses a dynamic array to store the minimum number of extra characters needed for each prefix of the string. For each end index i, we check all starting indices to see if a substring is in the dictionary and update the DP accordingly, minimizing extra characters added.
To solve the problem using a Trie and memoization, we first build a Trie from the dictionary. We then use a recursive function with memoization to attempt to decompose the string s into valid segments. For each position in the string, we check possible substrings against the Trie, saving calculated results to avoid redundant computations.
Time Complexity: O(N*M), with N being the string length and M the average dictionary word length due to Trie traversal.
Space Complexity: O(N + T), N is for the memo array and T is for Trie storage.
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
struct TrieNode {
unordered_map<char, TrieNode*> children;
bool isEnd = false;
};
class Trie {
public:
TrieNode* root;
Trie() { root = new TrieNode(); }
void insert(string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children[c])
node->children[c] = new TrieNode();
node = node->children[c];
}
node->isEnd = true;
}
};
int minExtraHelper(string& s, int idx, TrieNode* root, vector<int>& memo) {
int n = s.size();
if (idx == n) return 0;
if (memo[idx] != -1) return memo[idx];
int minExtra = n - idx;
TrieNode* node = root;
for (int i = idx; i < n; ++i) {
if (node->children.find(s[i]) == node->children.end()) break;
node = node->children[s[i]];
if (node->isEnd)
minExtra = min(minExtra, minExtraHelper(s, i + 1, root, memo));
}
minExtra = min(minExtra, 1 + minExtraHelper(s, idx + 1, root, memo));
return memo[idx] = minExtra;
}
int minExtraChars(string s, vector<string>& dictionary) {
Trie trie;
for (string word : dictionary)
trie.insert(word);
int n = s.size();
vector<int> memo(n, -1);
return minExtraHelper(s, 0, trie.root, memo);
}
int main() {
string s = "leetscode";
vector<string> dictionary = {"leet", "code", "leetcode"};
cout << minExtraChars(s, dictionary) << endl; // Output: 1
return 0;
}This C++ solution constructs a Trie from dictionary words and employs memoization to optimize the recursive decomposition of the string s. Using Trie, we efficiently check substrings while storing results of previous computations.