aboutsummaryrefslogtreecommitdiff
path: root/extra_char_string.py
blob: dd4b2af1af731ffef2c497016d03350887163bda (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 2707. Extra Characters in a String

"""
you are given a 0-indexed string 's' and a dictionary of words 'dictionary'.
you have to break 's' into one or more non-overlapping substrings 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
"""


class Solution(object):
    def func(self, idx, s, st, dp):
        if idx == len(s):
            return 0
        if dp[idx] != -1:
            return dp[idx]
        res = float("inf")
        for j in range(idx, len(s)):
            substr = s[idx : j + 1]
            if substr in st:
                res = min(res, 0 + self.func(j + 1, s, st, dp))
            else:
                res = min(res, j - idx + 1 + self.func(j + 1, s, st, dp))
        dp[idx] = res
        return res

    def minExtraChar(self, s, dictionary):
        dp = [-1] * (len(s) + 1)
        st = set(dictionary)
        return self.func(0, s, st, dp)


if __name__ == "__main__":
    obj = Solution()
    print(obj.minExtraChar("leetscode", ["leet", "code", "leetcode"]))  # expect: 1
    print(obj.minExtraChar("sayhelloworld", ["hello", "world"]))  # expect: 3