题目大意：
形成字符串的最短路径
对于任何字符串，我们可以通过删除其中一些字符（也可能不删除）来构造该字符串的子序列。
给定源字符串 source 和目标字符串 target，找出源字符串中能通过串联形成目标字符串的子序列的最小数量。如果无法通过串联源字符串中的子序列来构造目标字符串，则返回 -1。
示例 1：
输入：source = "abc", target = "abcbc" 输出：2 解释：目标字符串 "abcbc" 可以由 "abc" 和 "bc" 形成，它们都是源字符串 "abc" 的子序列。
示例 2：
输入：source = "abc", target = "acdbc" 输出：-1 解释：由于目标字符串中包含字符 "d"，所以无法由源字符串的子序列构建目标字符串。
示例 3：
输入：source = "xyz", target = "xzyxz" 输出：3 解释：目标字符串可以按如下方式构建： "xz" + "y" + "xz"。
提示：
source和target两个字符串都只包含 “a”-“z” 的英文小写字母。source和target两个字符串的长度介于1和1000之间。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1055
解题思路分析：
本题需要先对source字符串进行预处理，我们统计出2组信息，第一，字符串中每种字符首次出现的下标（没出现过的字符默认为-1）。第二，统计出每个下标后面距离它最近的a-z分别在哪里。
接下来我们先查看target的首字符在 source 中首次出现的位置sIndex，如果是-1，说明该字符不在 target 中，返回-1。如果存在，我们循环到target的下一位字符c，并且查看距离 sIndex 最近的字符c的位置，如果存在继续循环。反之如果不存在，说明当前子序列已经不能再继续下去，需要重头开始寻找新的子序列，此时返回结果加一，并且查看当前字符c在 source 中首次出现的位置，将该位置赋值给 sIndex ，继续重复上述操作，直到循环完 target 中所有字符为止。
实现代码：
public int shortestWay(String source, String target) {
// 保存source中每种字符首次出现的位置
int[] firstIndex=new int[26];
// 默认是-1（-1代表没出现过）
Arrays.fill(firstIndex, -1);
// 保存source字符串每个下标右侧距离他最近的a-z的位置
int[][] nextMap = new int[source.length()][26];
// 从后向前循环source每个字符
for(int i=source.length()-1;i>=0;i--){
if(i<source.length()-1){
// 赋值后一行信息后一行
nextMap[i]=Arrays.copyOf(nextMap[i+1],26);
// 后一个字符的位置为i+1
nextMap[i][source.charAt(i+1)-'a']=i+1;
}
// 更新当前字符首次出现位置
firstIndex[source.charAt(i)-'a']=i;
}
int res=1; // 返回结果
// target首字符在source中首次出现的位置
int sIndex=firstIndex[target.charAt(0)-'a'];
// 如果为-1，表示不存在，返回-1
if(sIndex==-1) return -1;
// 循环target的每个字符
for(int i=1;i<target.length();i++){
// 当前字符
int c = target.charAt(i)-'a';
// 查看source中距离下标sIndex最近的字符c的位置
sIndex=nextMap[sIndex][c];
// 如果为0，说明sIndex后不再存在该字符c，当前子序列结束
if(sIndex==0){
// 返回结果加一
res++;
// 查看当前字符在source中首次出现的位置
sIndex=firstIndex[c];
// 如果为-1，表示不存在，返回-1
if(sIndex==-1) return -1;
}
}
return res;
}本题解法执行时间为2ms。
Runtime: 2 ms, faster than 85.60% of Java online submissions for Shortest Way to Form String.
Memory Usage: 41 MB, less than 50.00% of Java online submissions for Shortest Way to Form String.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1055-shortest-way-to-form-string-解题思路分析/