#### 原题说明

From any string, we can form a subsequence of that string by deleting some number of characters (possibly no deletions).

Given two strings `source` and `target`, return the minimum number of subsequences of `source` such that their concatenation equals `target`. If the task is impossible, return `-1`.

Example 1:

`Input: source = “abc”, target = “abcbc”Output: 2Explanation: The target “abcbc” can be formed by “abc” and “bc”, which are subsequences of source “abc”.`

Example 2:

`Input: source = “abc”, target = “acdbc”Output: -1Explanation: The target string cannot be constructed from the subsequences of source string due to the character “d” in target string.`

Example 3:

`Input: source = “xyz”, target = “xzyxz”Output: 3Explanation: The target string can be constructed as follows “xz” + “y” + “xz”.`

Constraints:

• Both the `source` and `target` strings consist of only lowercase English letters from “a”-“z”.
• The lengths of `source` and `target` string are between `1` and `1000`.

#### 解题思路

`O(MN)`的解法较为直观，只需要用两个`index` `i``j`分别对应`source``target`的位置，然后对于每一个`target[j]`,在`source`中找到对应的`source[i]`, 并于每次i归零时计数即可。

1. `index_to_next[0]`当中是否存在`target[j]`，即整个`source`中是否存在`j`，不存在则返回`-1`
2. `index_to_next[i]`当中是否存在`target[j]`，如果不存在，说明`source`在位置`i`右侧不存在`target[j]``i`应当归零从头开始找
3. 如果`i == 0`，说明`source`被遍历了一边，返回值`round`应该增加1
4. 更新`i = index_to_next[i][target[i]]``source``i`右侧第一个`target[j]`的右侧的位置，这样相当于在`source`中读取了一个最近的`target[i]`
最后返回`round`即可。

#### 归纳总结

------ 关注公众号：猩猩的乐园 ------