2023-06-28:你想要用小写字母组成一个目标字符串 target。
开始的时候,序列由 target.length 个 '?' 记号组成
而你有一个小写字母印章 stamp。
在每个回合,你可以将印章放在序列上,并将序列中的每个字母替换为印章上的相应字母
你最多可以进行 10 * target.length 个回合
举个例子,如果初始序列为 "?????",而你的印章 stamp 是 "abc"
那么在第一回合,你可以得到 "abc??"、"?abc?"、"??abc"
(请注意,印章必须完全包含在序列的边界内才能盖下去。)
如果可以印出序列,那么返回一个数组,该数组由每个回合中被印下的最左边字母的索引组成
如果不能印出序列,就返回一个空数组。
例如,如果序列是 "ababc",印章是 "abc"
那么我们就可以返回与操作 "?????" -> "abc??" -> "ababc" 相对应的答案 [0, 2]
另外,如果可以印出序列,那么需要保证可以在 10 * target.length 个回合内完成
任何超过此数字的答案将不被接受。
输入:stamp = "abc", target = "ababc"。
输出:[0,2]。
答案2023-06-28:
大体步骤如下:
1.创建变量s和t,分别存储印章stamp和目标字符串target的字节数组表示。
2.创建变量m和n,分别存储印章长度和目标字符串长度。
3.创建数组inDegrees,长度为n-m+1,初始化每个元素为m。该数组表示每个位置需要匹配的印章字符数量。
4.创建二维数组graph,长度为n,每个位置是一个空的整数数组。该数组表示目标字符串每个位置对应的可能的匹配位置。
5.创建队列queue,长度为n-m+1,用于存储已经匹配完所有印章字符的位置。
6.创建变量l和r,分别表示队列queue的左右指针,初始时都为0。
7.遍历目标字符串,从0到n-m,依次处理每个位置:
7.1.在当前位置i,遍历印章的每个字符:
7.1.1.若目标字符串t的第i+j个字符与印章字符相等,表示匹配成功,更新inDegrees数组,将对应位置的值减1。
7.1.1.1.如果经过减1操作后,该位置上印章字符匹配数量变为0,将该位置加入队列queue,并将右指针r向右移动。
7.1.2. 若目标字符串t的第i+j个字符与印章字符不相等,表示匹配失败,将该位置加入graph[i+j]数组中,表示可以在该位置之后的某个位置尝试匹配印章。
8.创建bool类型的数组visited,长度为n,用于标记目标字符串的位置是否被访问过。
9.创建数组path,长度为n-m+1,用于记录完成印章替换的顺序。
10.创建变量size,初始为0,表示已经完成替换的印章的数量。
11.当左指针l小于右指针r时,执行以下循环:
11.1.取出队列queue中的当前位置cur,并将左指针l右移。
11.2.将当前位置cur加入数组path中,并增加size的值。
11.3.遍历印章的每个字符:
11.3.1.若当前位置cur+i未被访问过,表示可以尝试在该位置继续匹配印章:
11.3.1.1.将该位置标记为已访问visited[cur+i] = true。
11.3.1.2.遍历当前位置cur+i对应的graph数组中的每个位置next:
11.3.1.2.1.更新inDegrees数组,将对应位置的值减1。
11.3.1.2.1.1.如果经过减1操作后,该位置上印章字符匹配数量变为0,将该位置加入队列queue,并将右指针r向右移动。
12.检查完成替换的印章数量是否等于n-m+1,如果不相等,返回空数组[]。
13.将数组path中的元素按照首尾对称的顺序重新排列,即交换元素path[i]和path[j],其中i从0遍历到size-1,j从size-1遍历到0。
14.返回数组path作为结果。
该程序的总时间复杂度和总空间复杂度为:
总时间复杂度:O((n - m + 1) * m),其中n是target字符串的长度,m是stamp字符串的长度。
总空间复杂度:O(n),其中n是target字符串的长度。
go完整代码如下:
在这里插入图片描述rust完整代码如下:
在这里插入图片描述c++完整代码如下:
在这里插入图片描述
领取专属 10元无门槛券
私享最新 技术干货