[Python3] Sliding Window + DP
Intuition\n Describe your first thoughts on how to solve this problem. \n\nExpand the right side of window when prefix is valid, otherwise expand the left side.
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nExpand the right side of window when `prefix is valid`, otherwise expand the left side.\n\nStore the computation result with dp, `dp[right] = dp[left] + 1`\n\n# Code\n```python3 []\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        left = 0\n        right = 1\n        n = len(target)\n        dp = [0] * (n + 1)\n\n        while right <= n:\n            if left == right:\n                return -1\n            if self.isValidPrefix(words, target[left:right]):    \n                dp[right] = dp[left] + 1\n                right += 1\n            else:\n                left += 1\n        return dp[-1]\n\n\n    def isValidPrefix(self, words, prefix):\n        for word in words:\n            if word.startswith(prefix):\n                return True\n        return False\n```
['Python3']