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.
using System.Collections.Generic;
public class Solution {
public int MinExtraChars(string s, IList<string> dictionary) {
var dictSet = new HashSet<string>(dictionary);
int n = s.Length;
var dp = new int[n + 1];
Array.Fill(dp, n);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + 1;
for (int j = 0; j < i; j++) {
if (dictSet.Contains(s.Substring(j, i - j))) {
dp[i] = Math.Min(dp[i], dp[j]);
}
}
}
return dp[n];
}
public static void Main(string[] args) {
var solution = new Solution();
string s = "leetscode";
IList<string> dictionary = new List<string>{"leet", "code", "leetcode"};
Console.WriteLine(solution.MinExtraChars(s, dictionary)); // Output: 1
}
}The C# solution employs a HashSet for efficient dictionary lookups and utilizes a dynamic programming approach to minimize the count of extra characters by evaluating substrings.
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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define ALPHABET_SIZE 26
6
7typedef struct TrieNode {
8 struct TrieNode *children[ALPHABET_SIZE];
9 int isEndOfWord;
10} TrieNode;
11
12TrieNode *getNode(void) {
13 TrieNode *newNode = (TrieNode *)malloc(sizeof(TrieNode));
14 newNode->isEndOfWord = 0;
15 for (int i = 0; i < ALPHABET_SIZE; i++)
16 newNode->children[i] = NULL;
17 return newNode;
18}
19
20void insertTrie(TrieNode *root, const char *key) {
21 TrieNode *levelNode = root;
22 for (int i = 0; key[i]; i++) {
23 int index = key[i] - 'a';
24 if (!levelNode->children[index])
25 levelNode->children[index] = getNode();
26 levelNode = levelNode->children[index];
27 }
28 levelNode->isEndOfWord = 1;
29}
30
31int searchTrie(TrieNode *root, const char *str, int start, int end) {
32 TrieNode *levelNode = root;
33 for (int i = start; i < end; i++) {
34 int index = str[i] - 'a';
35 if (!levelNode->children[index])
36 return 0;
37 levelNode = levelNode->children[index];
38 }
39 return levelNode->isEndOfWord;
40}
41
42int minExtraHelper(char *s, int n, int idx, TrieNode *root, int *memo) {
43 if (idx == n) return 0;
44 if (memo[idx] != -1) return memo[idx];
45 int minExtra = n - idx;
46 for (int i = idx + 1; i <= n; i++) {
47 if (searchTrie(root, s, idx, i)) {
48 minExtra = (minExtra < minExtraHelper(s, n, i, root, memo)) ?
49 minExtra : mirror(minExtraHelper(s, n, i, root, memo));
50 }
51 }
52 minExtra = (minExtra < 1 + minExtraHelper(s, n, idx + 1, root, memo)) ?
53 minExtra : 1 + minExtraHelper(s, n, idx + 1, root, memo);
54 return memo[idx] = minExtra;
55}
56
57int minExtraChars(char *s, char dictionary[][51], int dictionarySize) {
58 TrieNode *root = getNode();
59 for (int i = 0; i < dictionarySize; i++)
60 insertTrie(root, dictionary[i]);
61
62 int n = strlen(s);
63 int memo[n];
64 for (int i = 0; i < n; i++)
65 memo[i] = -1;
66
67 return minExtraHelper(s, n, 0, root, memo);
68}
69
70int main() {
71 char s[] = "leetscode";
72 char dictionary[][51] = {"leet", "code", "leetcode"};
73 int dictionarySize = 3;
74 int result = minExtraChars(s, dictionary, dictionarySize);
75 printf("%d\n", result); // Output: 1
76 return 0;
77}This C solution utilizes a Trie to store dictionary words for fast matching. It also uses memoization to recursively find the minimum extra characters. Each call attempts to split the string from the current index, using the Trie to validate substrings.