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.
1import java.util.*;
2
3public class Main {
4 public static int minExtraChars(String s, List<String> dictionary) {
5 Set<String> dictSet = new HashSet<>(dictionary);
6 int n = s.length();
7 int[] dp = new int[n + 1];
8 Arrays.fill(dp, n);
9 dp[0] = 0;
10
11 for (int i = 1; i <= n; i++) {
12 dp[i] = dp[i - 1] + 1;
13 for (int j = 0; j < i; j++) {
14 if (dictSet.contains(s.substring(j, i))) {
15 dp[i] = Math.min(dp[i], dp[j]);
16 }
17 }
18 }
19 return dp[n];
20 }
21
22 public static void main(String[] args) {
23 String s = "leetscode";
24 List<String> dictionary = Arrays.asList("leet", "code", "leetcode");
25 int result = minExtraChars(s, dictionary);
26 System.out.println(result); // Output: 1
27 }
28}This Java solution uses a set to store dictionary words for quick lookups. Dynamic programming is used to compute minimum extra characters by examining all substrings ending at each position in s.
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.
using System.Collections.Generic;
class TrieNode {
public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
public bool IsEnd;
}
class Trie {
public TrieNode Root = new TrieNode();
public void Insert(string word) {
var node = Root;
foreach (var ch in word) {
if (!node.Children.ContainsKey(ch))
node.Children[ch] = new TrieNode();
node = node.Children[ch];
}
node.IsEnd = true;
}
}
class Solution {
private int MinExtraHelper(string s, int idx, TrieNode root, int[] memo) {
int n = s.Length;
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.ContainsKey(s[i])) break;
node = node.Children[s[i]];
if (node.IsEnd)
minExtra = Math.Min(minExtra, MinExtraHelper(s, i + 1, root, memo));
}
minExtra = Math.Min(minExtra, 1 + MinExtraHelper(s, idx + 1, root, memo));
return memo[idx] = minExtra;
}
public int MinExtraChars(string s, List<string> dictionary) {
Trie trie = new Trie();
foreach (var word in dictionary)
trie.Insert(word);
int n = s.Length;
int[] memo = new int[n];
Array.Fill(memo, -1);
return MinExtraHelper(s, 0, trie.Root, memo);
}
static void Main(string[] args) {
var s = "leetscode";
var dictionary = new List<string> { "leet", "code", "leetcode" };
var solution = new Solution();
Console.WriteLine(solution.MinExtraChars(s, dictionary)); // Output: 1
}
}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.