Devin's Blog

Extra Characters In A String

2 min read

TARGET DECK: Leetcode FILE TAGS: Medium

Intuition

  • For bottom up, I follow a similar design to Word Break.
  • The main difference between Word Break and this problem is:
    • Rather than asking for “tell me whether I can fill the entire string with words from my dictionary” it is:
      • Tell me the characters that remain after maximally filling the string.
  • Therefore, the following alterations are made:
    • Rather than storing True/False wherein True/False means “store whether or not the entire string can be filled”, each DP slot stores the minimal alterations needed given that prefix.
  • More specifically:
    • Check if the words you are comparing fill the prefix given the prior computed prefixes.
    • For example, if you have leetscode, then what you must chop off from that prefix is “leets” with “code” remaining.
    • Then you can check dp[“leets”] to find how many characters you had to left from that prefix.
    • However, be careful of getting the word that has the most bang for your buck on that prefix. The more you can remove, or the less you can chop off to get the word, the better.

Complexity

Runtime

Space

Code

Top Down

Todo

Still remains.

Bottom Up

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        n = len(s)
        dp = [0] * (n + 1)
 
        for i in range(1, n + 1):
            prefix = s[:i]
            dp[i] = 1 + dp[i - 1]
 
            for word in dictionary:
                chop = len(prefix) - len(word) # Amount of letters to remove to keep the word in question on the prefix
                if chop >= 0 and word == prefix[chop:]:
                    dp[i] = min(dp[i], dp[chop]) # The more letters that weren't chopped, the better
 
        return dp[n]

Notes

Cards

START Basic Front: Extra Characters In A String Back: Each subproblem is a prefix which you remove the maximal amount from, given previous prefixes.

END

References

Graph View