⚡Flashcard Drill➔
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

  1. This is a word-break DP with a cost: dp[i] is the minimum extra characters for the suffix s[i:].
  2. At each position, either skip s[i] (cost 1) or use a dictionary word starting there (cost 0 for the covered part).
  3. So dp[i] = min(dp[i+1] + 1, min over matching words w of dp[i + len(w)]).
  4. A trie or a hash set makes the word lookup fast; the DP is over n positions.

💻 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] for j > 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.
🎯 Drill This Card Now➔

🧩 Related Tries Problems