NeetCode #480LC-2707MediumTriesNC 250
← Back to All Problems#480 · #2707 · Extra Characters in a String(字符串中的额外字符)
📌 Problem Statement & Constraints
You are given a string
s and a dictionary of words. Break s into the dictionary words plus leftover single characters; return the minimum number of leftover characters. Constraints: 1 <= s.length <= 50, 1 <= dictionary.length <= 50, word lengths up to 50.💡 Core Algorithmic Approaches
- This is a word-break DP with a cost:
dp[i]is the minimum extra characters for the suffixs[i:]. - At each position, either skip
s[i](cost 1) or use a dictionary word starting there (cost 0 for the covered part). - So
dp[i] = min(dp[i+1] + 1, min over matching words w of dp[i + len(w)]). - A trie or a hash set makes the word lookup fast; the DP is over
npositions.
💻 Benchmark Python3 Implementation
class Solution:
def minExtraChar(self, s: str, dictionary: List[str]) -> int:
words = set(dictionary)
n = len(s)
dp = [0] * (n + 1) # dp[i] = extra chars needed for s[i:]
for i in range(n - 1, -1, -1):
dp[i] = dp[i + 1] + 1 # option 1: leave s[i] unused
for j in range(i + 1, n + 1):
if s[i:j] in words: # option 2: use a dictionary word
dp[i] = min(dp[i], dp[j])
return dp[0]
# Trie variant: avoids materialising every substring
class Solution2:
def minExtraChar(self, s: str, dictionary: List[str]) -> int:
root = {}
for w in dictionary:
node = root
for ch in w:
node = node.setdefault(ch, {})
node["#"] = True
n = len(s)
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
dp[i] = dp[i + 1] + 1
node = root
for j in range(i, n):
if s[j] not in node:
break # no dictionary word continues this way
node = node[s[j]]
if "#" in node:
dp[i] = min(dp[i], dp[j + 1])
return dp[0]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2) for the set-based version (substring hashing), O(n * L) for the trie version.
💾 Space Complexity
O(n) for the DP plus the dictionary storage.
⚠️ Interview Pitfalls & Follow-ups
- Maximising the covered length instead of minimising the leftovers: the two are equivalent, but the DP must be written consistently.
- Iterating forward with the wrong direction: the recurrence reads
dp[j]forj > i, so the loop runs backwards. - Forgetting the skip option: leaving a character unused is always allowed and gives the baseline
dp[i+1] + 1. - Assuming the whole string can be covered: it need not be, hence the cost model.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.