思路简单,也好写。
只有一种方法会返回-1,就是target里面有source中不存在的字符。
剩下的情况这么处理:
有一个局部string,叫做cur,表示从上次匹配成功后变成的字符串。
这个听起来挺奇怪的哈。
比如source是abc,target是abab,字符串按照顺序遍历到第一个字符时cur=a,此时cur是abc的子序列。dp[i]=dp[i-1]第二个字符ab时也是,dp[i]=dp[i-1]。当遍历到第三个字符aba时,明显cur就不是abc的子序列。此时dp[i]=dp[i-1]+1,而cur清零后重置为target[2]
对于任何字符串,我们可以通过删除其中一些字符(也可能不删除)来构造该字符串的 子序列 。(例如,“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”。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/shortest-way-to-form-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
bool isSub(string a,string b)
{
int an=static_cast(a.size()),bn=static_cast(b.size());
int ai=0,bi=0;
while(aivisited;
for(auto cha:source)
visited.insert(cha);
for(auto cha:target)
if(visited.find(cha)==visited.end())
return -1;
int n = static_cast(target.size());
vectordp(n,0);
string cur = "" ;
cur += target[0];
dp[0] = 1;
for(int i=1;i