class Solution {
public:
int shortestWay(string source, string target) {
}
};
1055. 形成字符串的最短路径
对于任何字符串，我们可以通过删除其中一些字符（也可能不删除）来构造该字符串的 子序列 。(例如，“ace” 是 “abcde” 的子序列，而 “aec” 不是)。
给定源字符串 source 和目标字符串 target，返回 源字符串 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 <= source.length, target.length <= 1000source 和 target 仅包含英文小写字母。相似题目
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-10-22 10:27:00
func shortestWay(source string, target string) int {
// 源字符串中所有字符的索引列表
charToIndices := make([][]int, 26)
for i := 0; i < len(source); i++ {
c := source[i]
if charToIndices[c-'a'] == nil {
charToIndices[c-'a'] = make([]int, 0)
}
charToIndices[c-'a'] = append(charToIndices[c-'a'], i)
}
// 源字符串的指针
sourceIterator := 0
// 我们需要在源字符串上进行迭代的次数
count := 1
// 在源字符串中找到目标字符串的所有字符
for _, c := range target {
// 如果源字符串中不存在该字符，返回 -1
if charToIndices[c-'a'] == nil {
return -1
}
// 二分查找
// 找出源迭代器旁边的字符在源字符串中的索引
indices := charToIndices[c-'a']
index := sort.Search(len(indices), func(i int) bool {
return indices[i] >= sourceIterator
})
// 如果我们已经到达列表的末尾，我们需要重新遍历源字符串
// 因此需要找到字符在源字符串中的第一个索引。
if index == len(indices) {
count++
sourceIterator = indices[0] + 1
} else {
sourceIterator = indices[index] + 1
}
}
// 返回我们需要在源字符串上进行迭代的次数
return count
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.9 MB, 提交时间: 2023-10-22 10:25:40
class Solution {
public:
int shortestWay(string source, string target) {
int sp = 0, tp = 0, ans = 1;
int sn = source.size(), tn = target.size();
while(tp < tn){
while(sp < sn && source[sp] != target[tp]) ++sp;
if(sp == sn) {
sp = 0;
++ans;
while(sp < sn && source[sp] != target[tp]) ++sp;
if(sp == sn) return -1;
}
++sp, ++tp;
}
return ans;
}
};
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.7 MB, 提交时间: 2023-10-22 10:25:29
class Solution {
public:
int update(const string& target, int i, const string& source) {
int j = 0;
while (i < target.size() && j < source.size()) {
if (target[i] == source[j]) {
++i;
++j;
} else {
++j;
}
}
return i;
}
int shortestWay(string source, string target) {
int i = 0;
int res = 0;
while (i < target.size()) {
++res;
int t = update(target, i, source);
if (t == i) return -1;
i = t;
}
return res;
}
};
java 解法, 执行用时: 4 ms, 内存消耗: 39.4 MB, 提交时间: 2023-10-22 10:25:13
class Solution {
public int shortestWay(String source, String target) {
int n = source.length();
int j = 0 ;
int count = 0 ;
while( j < target.length() ){
int prev = j ;
for(int i = 0 ; i < n ; i++){
if( j < target.length() && source.charAt(i) == target.charAt(j) )
j++;
}
if( prev == j ) //如果j没有移动
return -1;
count++;
}
return count ;
}
}