# 动态规划的解法，参考别人的。
from typing import List
class Solution:
    def respace(self, dictionary: List[str], sentence: str) -> int:
        d = {}.fromkeys(dictionary,"heheh")
        length = len(sentence)
        f = [0] * (length + 1)
        for index in range(1,length + 1):
            f[index] = f[index - 1] + 1
            for index1 in range(index):
                if sentence[index1:index] in d:
                    f[index] = min(f[index],f[index1])
        print(f)
        return f[-1]
A = Solution()
# print(A.respace(["looked","just","like","her","brother"],"jesslookedjustliketimherbrother"))
print(A.respace(["aaysaayayaasyya","yyas","yayysaaayasasssy","yaasassssssayaassyaayaayaasssasysssaaayysaaasaysyaasaaaaaasayaayayysasaaaa","aya","sya","ysasasy","syaaaa","aaaas","ysa","a","aasyaaassyaayaayaasyayaa","ssaayayyssyaayyysyayaasaaa","aya","aaasaay","aaaa","ayyyayssaasasysaasaaayassasysaaayaassyysyaysaayyasayaaysyyaasasasaayyasasyaaaasysasy","aaasa","ysayssyasyyaaasyaaaayaaaaaaaaassaaa","aasayaaaayssayyaayaaaaayaaays","s"],"asasayaayaassayyayyyyssyaassasaysaaysaayaaaaysyaaaa"))