X

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

题目大意:

形成字符串的最短路径

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

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

提示:

  1. sourcetarget 两个字符串都只包含 “a”-“z” 的英文小写字母。
  2. sourcetarget 两个字符串的长度介于 11000 之间。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: 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-解题思路分析/
Categories: leetcode
kwantong: