LeetCode

题目大意：

形成字符串的最短路径

对于任何字符串，我们可以通过删除其中一些字符（也可能不删除）来构造该字符串的子序列。

给定源字符串 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.

本文转载自 https://leetcode.jp/

LEETCODE 1055. Shortest Way to Form String 解题思路分析