short kmp + greedy solution
\ndef minValidStrings(self, words: List[str], tar: str) -> int:\n    def kmp(strs):\n        s, dp = strs+\'|\'+tar, [0]*(len(strs)+len(tar)+1)\n        for i i
```\ndef minValidStrings(self, words: List[str], tar: str) -> int:\n    def kmp(strs):\n        s, dp = strs+\'|\'+tar, [0]*(len(strs)+len(tar)+1)\n        for i in range(1, len(s)):\n            k = dp[i-1]\n            while k and s[i]!=s[k]:\n                k = dp[k-1]\n            dp[i] = k+(s[i]==s[k])\n        return dp[len(strs):]\n\n    dp, p = [0]+[inf]*len(tar), [0]*(len(tar)+1)\n    for w in words:\n        p = [max(i, j) for i, j in zip(p, kmp(w))]\n    for i in range(1, len(tar)+1):\n        if i-p[i]>=0:\n            dp[i] = min(dp[i], dp[i-p[i]]+1)\n    return dp[-1] if dp[-1]<inf else -1\n```
[]