extra_characters_in_a_string

View Source

 1from functools import cache
 2# @leet start
 3class Solution:
 4	def minExtraChar(self, s: str, dictionary: list[str]) -> int:
 5		"""
 6		This question asks us to figure out how to create the minimum string given
 7		a dictionary where you can remove a substring if it exists in the dictionary.
 8		We can use every word in the dictionary as many times as we want to.
 9
10		We can look at this as an edit distance-esque question:
11		1. Given an empty string, we return 0, since there are 0 extra characters.
12		2. If the string is not empty, we try to match any of the words in the dictionary,
13		starting at the beginning of the string. If we find a match, we recurse with that
14		substring, trying to find the smallest resulting string.
15		3. We also check what happens if we skip the current string, so we increment
16		our pointer into the string by one and return the dfs of its result + 1.
17
18		At the end, the minimum dfs length is the one we want to keep.
19		"""
20		@cache
21		def dfs(s):
22			if not s:
23				return 0
24			dfses = []
25			skip = dfs(s[1:]) + 1
26			for word in dictionary:
27				if s.startswith(word):
28					dfses.append(dfs(s[len(word):]))
29			dfses.append(len(s))
30			dfses.append(skip)
31			return min(dfses)
32		return dfs(s)
33
34
35# @leet end
36
37def test():
38	assert(2 + 2 == 4)

class Solution: View Source

 4class Solution:
 5	def minExtraChar(self, s: str, dictionary: list[str]) -> int:
 6		"""
 7		This question asks us to figure out how to create the minimum string given
 8		a dictionary where you can remove a substring if it exists in the dictionary.
 9		We can use every word in the dictionary as many times as we want to.
10
11		We can look at this as an edit distance-esque question:
12		1. Given an empty string, we return 0, since there are 0 extra characters.
13		2. If the string is not empty, we try to match any of the words in the dictionary,
14		starting at the beginning of the string. If we find a match, we recurse with that
15		substring, trying to find the smallest resulting string.
16		3. We also check what happens if we skip the current string, so we increment
17		our pointer into the string by one and return the dfs of its result + 1.
18
19		At the end, the minimum dfs length is the one we want to keep.
20		"""
21		@cache
22		def dfs(s):
23			if not s:
24				return 0
25			dfses = []
26			skip = dfs(s[1:]) + 1
27			for word in dictionary:
28				if s.startswith(word):
29					dfses.append(dfs(s[len(word):]))
30			dfses.append(len(s))
31			dfses.append(skip)
32			return min(dfses)
33		return dfs(s)

def minExtraChar(self, s: str, dictionary: list[str]) -> int: View Source

 5	def minExtraChar(self, s: str, dictionary: list[str]) -> int:
 6		"""
 7		This question asks us to figure out how to create the minimum string given
 8		a dictionary where you can remove a substring if it exists in the dictionary.
 9		We can use every word in the dictionary as many times as we want to.
10
11		We can look at this as an edit distance-esque question:
12		1. Given an empty string, we return 0, since there are 0 extra characters.
13		2. If the string is not empty, we try to match any of the words in the dictionary,
14		starting at the beginning of the string. If we find a match, we recurse with that
15		substring, trying to find the smallest resulting string.
16		3. We also check what happens if we skip the current string, so we increment
17		our pointer into the string by one and return the dfs of its result + 1.
18
19		At the end, the minimum dfs length is the one we want to keep.
20		"""
21		@cache
22		def dfs(s):
23			if not s:
24				return 0
25			dfses = []
26			skip = dfs(s[1:]) + 1
27			for word in dictionary:
28				if s.startswith(word):
29					dfses.append(dfs(s[len(word):]))
30			dfses.append(len(s))
31			dfses.append(skip)
32			return min(dfses)
33		return dfs(s)

This question asks us to figure out how to create the minimum string given a dictionary where you can remove a substring if it exists in the dictionary. We can use every word in the dictionary as many times as we want to.

We can look at this as an edit distance-esque question:

Given an empty string, we return 0, since there are 0 extra characters.
If the string is not empty, we try to match any of the words in the dictionary, starting at the beginning of the string. If we find a match, we recurse with that substring, trying to find the smallest resulting string.
We also check what happens if we skip the current string, so we increment our pointer into the string by one and return the dfs of its result + 1.

At the end, the minimum dfs length is the one we want to keep.

def test(): View Source

38def test():
39	assert(2 + 2 == 4)