minimum-number-of-valid-strings-to-form-target-ii
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```golang []\nfunc minValidStrings(words []string, target string) int {\n    n := len(target)\n    match := make([]int, n)\n\n    for _, word := range words {\n        s := word + "#" + target\n        excess := len(word) + 1\n        nn := len(s)\n        z := make([]int, nn)\n        x, y := 0, 0\n\n        for i := 1; i < nn; i++ {\n            if i <= y {\n                z[i] = min(y - i + 1, z[i - x])\n            }\n            for i+z[i] < nn && s[z[i]] == s[i+z[i]] {\n                z[i]++\n            }\n            if i+z[i]-1 > y {\n                x = i\n                y = i + z[i] - 1\n            }\n            if i >= excess && z[i] > 0 {\n                pos := i - excess\n                if match[pos] < z[i] {\n                    match[pos] = z[i]\n                }\n            }\n        }\n    }\n\n    // \u0416\u0430\u0434\u043D\u044B\u0439 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\n    steps := 0\n    currEnd := 0\n    farthest := 0\n\n    for i := 0; i < n; i++ {\n        if i+match[i] > farthest {\n            farthest = i + match[i]\n        }\n        if i == currEnd {\n            if farthest <= i {\n                return -1\n            }\n            steps++\n            currEnd = farthest\n            if currEnd >= n {\n                break\n            }\n        }\n    }\n\n    if currEnd < n {\n        return -1\n    }\n    return steps\n}\n\nfunc min(a, b int) int {\n    if a < b {\n        return a\n    }\n    return b\n}\n```
['Go']