Welcome to Subscribe On Youtube
2707. Extra Characters in a String
Description
You are given a 0indexed string s
and a dictionary of words dictionary
. You have to break s
into one or more nonoverlapping 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]
ands
consists of only lowercase English lettersdictionary
contains distinct words
Solutions
Solution 1: Hash Table + Dynamic Programming
We can use a hash table $ss$ to record all words in the dictionary, which allows us to quickly determine whether a string is in the dictionary.
Next, we define $f[i]$ to represent the minimum number of extra characters in the first $i$ characters of string $s$, initially $f[0] = 0$.
When $i \ge 1$, the $i$th character $s[i  1]$ can be an extra character, in which case $f[i] = f[i  1] + 1$. If there exists an index $j \in [0, i  1]$ such that $s[j..i)$ is in the hash table $ss$, then we can take $s[j..i)$ as a word, in which case $f[i] = f[j]$.
In summary, we can get the state transition equation:
\[f[i] = \min \{ f[i  1] + 1, \min_{j \in [0, i  1]} f[j] \}\]where $i \ge 1$, and $j \in [0, i  1]$ and $s[j..i)$ is in the hash table $ss$.
The final answer is $f[n]$.
The time complexity is $O(n^3 + L)$, and the space complexity is $O(n + L)$. Here, $n$ is the length of string $s$, and $L$ is the sum of the lengths of all words in the dictionary.
Solution 2: Trie + Dynamic Programming
We can use a trie to optimize the time complexity of Solution 1.
Specifically, we first insert each word in the dictionary into the trie $root$ in reverse order, then we define $f[i]$ to represent the minimum number of extra characters in the first $i$ characters of string $s$, initially $f[0] = 0$.
When $i \ge 1$, the $i$th character $s[i  1]$ can be an extra character, in which case $f[i] = f[i  1] + 1$. We can also enumerate the index $j$ in reverse order in the range $[0..i1]$, and determine whether $s[j..i)$ is in the trie $root$. If it exists, then we can take $s[j..i)$ as a word, in which case $f[i] = f[j]$.
The time complexity is $O(n^2 + L)$, and the space complexity is $O(n + L \times \Sigma)$. Here, $n$ is the length of string $s$, and $L$ is the sum of the lengths of all words in the dictionary. Additionally, $\Sigma$ is the size of the character set. In this problem, the character set is lowercase English letters, so $\Sigma = 26$.

class Solution { public int minExtraChar(String s, String[] dictionary) { Set<String> ss = new HashSet<>(); for (String w : dictionary) { ss.add(w); } int n = s.length(); int[] f = new int[n + 1]; f[0] = 0; for (int i = 1; i <= n; ++i) { f[i] = f[i  1] + 1; for (int j = 0; j < i; ++j) { if (ss.contains(s.substring(j, i))) { f[i] = Math.min(f[i], f[j]); } } } return f[n]; } }

class Solution { public: int minExtraChar(string s, vector<string>& dictionary) { unordered_set<string> ss(dictionary.begin(), dictionary.end()); int n = s.size(); int f[n + 1]; f[0] = 0; for (int i = 1; i <= n; ++i) { f[i] = f[i  1] + 1; for (int j = 0; j < i; ++j) { if (ss.count(s.substr(j, i  j))) { f[i] = min(f[i], f[j]); } } } return f[n]; } };

class Solution: def minExtraChar(self, s: str, dictionary: List[str]) > int: ss = set(dictionary) n = len(s) f = [0] * (n + 1) for i in range(1, n + 1): f[i] = f[i  1] + 1 for j in range(i): if s[j:i] in ss and f[j] < f[i]: f[i] = f[j] return f[n]

func minExtraChar(s string, dictionary []string) int { ss := map[string]bool{} for _, w := range dictionary { ss[w] = true } n := len(s) f := make([]int, n+1) for i := 1; i <= n; i++ { f[i] = f[i1] + 1 for j := 0; j < i; j++ { if ss[s[j:i]] && f[j] < f[i] { f[i] = f[j] } } } return f[n] }

function minExtraChar(s: string, dictionary: string[]): number { const ss = new Set(dictionary); const n = s.length; const f = new Array(n + 1).fill(0); for (let i = 1; i <= n; ++i) { f[i] = f[i  1] + 1; for (let j = 0; j < i; ++j) { if (ss.has(s.substring(j, i))) { f[i] = Math.min(f[i], f[j]); } } } return f[n]; }

use std::collections::HashSet; impl Solution { pub fn min_extra_char(s: String, dictionary: Vec<String>) > i32 { let ss: HashSet<String> = dictionary.into_iter().collect(); let n = s.len(); let mut f = vec![0; n + 1]; for i in 1..=n { f[i] = f[i  1] + 1; for j in 0..i { if ss.contains(&s[j..i]) { f[i] = f[i].min(f[j]); } } } f[n] } }