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.
The Python solution employs a set for the dictionary and a dynamic programming array to calculate the minimum extra characters for each prefix length, checking substrings against the dictionary.
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.
1using System;
2using System.Collections.Generic;
3
4class TrieNode {
5 public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
6 public bool IsEnd;
7}
8
9class Trie {
10 public TrieNode Root = new TrieNode();
11
12 public void Insert(string word) {
13 var node = Root;
14 foreach (var ch in word) {
15 if (!node.Children.ContainsKey(ch))
16 node.Children[ch] = new TrieNode();
17 node = node.Children[ch];
18 }
19 node.IsEnd = true;
20 }
21}
22
23class Solution {
24 private int MinExtraHelper(string s, int idx, TrieNode root, int[] memo) {
25 int n = s.Length;
26 if (idx == n) return 0;
27 if (memo[idx] != -1) return memo[idx];
28 int minExtra = n - idx;
29 TrieNode node = root;
30 for (int i = idx; i < n; i++) {
31 if (!node.Children.ContainsKey(s[i])) break;
32 node = node.Children[s[i]];
33 if (node.IsEnd)
34 minExtra = Math.Min(minExtra, MinExtraHelper(s, i + 1, root, memo));
35 }
36 minExtra = Math.Min(minExtra, 1 + MinExtraHelper(s, idx + 1, root, memo));
37 return memo[idx] = minExtra;
38 }
39
40 public int MinExtraChars(string s, List<string> dictionary) {
41 Trie trie = new Trie();
42 foreach (var word in dictionary)
43 trie.Insert(word);
44 int n = s.Length;
45 int[] memo = new int[n];
46 Array.Fill(memo, -1);
47 return MinExtraHelper(s, 0, trie.Root, memo);
48 }
49
50 static void Main(string[] args) {
51 var s = "leetscode";
52 var dictionary = new List<string> { "leet", "code", "leetcode" };
53 var solution = new Solution();
54 Console.WriteLine(solution.MinExtraChars(s, dictionary)); // Output: 1
55 }
56}This C# solution constructs a Trie for dictionary look-up and uses a recursive approach with memoization to optimize computations, reducing the number of unmatched characters by leveraging the Trie to find valid words swiftly.