你想要用小写字母组成一个目标字符串  target 。
开始的时候，序列由  target.length 个  '?'  记号组成。而你有一个小写字母印章  stamp 。
在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母。你最多可以进行  10 * target.length 个回合。
举个例子，如果初始序列为 "?????"，而你的印章  stamp  是  "abc" ，那么在第一回合，你可以得到 "abc??"、"?abc?"、"??abc"。（请注意，印章必须完全包含在序列的边界内才能盖下去。）
如果可以印出序列，那么返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成。如果不能印出序列，就返回一个空数组。
例如，如果序列是 "ababc"，印章是 "abc" ，那么我们就可以返回与操作 "?????" -> "abc??" -> "ababc" 相对应的答案  [0, 2] ；
另外，如果可以印出序列，那么需要保证可以在  10 * target.length  个回合内完成。任何超过此数字的答案将不被接受。
1.1 <= stamp.length <= target.length <= 1000
2.stamp 和 target 仅包含小写字母。
在线评测地址： https://www.lintcode.com/problem/median-of-two-sorted-arrays/?utm_source=sc-v2ex-fks
样例 1: 输入：stamp = "abc", target = "ababc" 输出：[0,2] 解释："?????"->"abc??"->"ababc"
样例 2: 输入：stamp = "abca", target = "aabcaca" 输出：[3,0,1] 解释："???????"->"???abca"->"abcabca"->"aabcaca"
[题解]
考点： 贪心 字符串
题解： 考虑下面的样例 Stamp = "abc", Target = "ababcbc" Target = ab???bc Target = ab????? Target = ??????? 逆向做法，可以在 target 中找到 stamp 的子串。然后用特殊符号覆盖。我们逆向想一下，因为我后盖的章会覆盖掉前面的章，那么我前面的章无论什么时候盖对后盖的章都是没有影响的，所以我先找到最后一次章盖的位置，即在 target 序列中找 stamp，记下盖的序列的最左边位置，然后把相应位置全部替换为‘?’，相当于就是例 2 中的 "a????ca"，然后把这个？看成一个万能的字母，它可以为任意的，再找 stamp，这样，一直到最后全部变成 target，这些序列就是从最后一次到第一次盖章的位置，然后倒转一下就是题目所要求的。需要注意的是，在写代码的时候，一定要注意需要判断匹配的字符串可能全是?，所以需要防止这种情况产生。 class Solution { public int[] movesToStamp(String stamp, String target) { char[] S = stamp.toCharArray(); char[] T = target.toCharArray(); List<Integer> res = new ArrayList<>(); boolean[] visited = new boolean[T.length]; int stars = 0; while (stars < T.length) { boolean doneReplace = false; for (int i = 0; i <= T.length - S.length; i++) { if (!visited[i] && canReplace(T, i, S)) { stars = doReplace(T, i, S.length, stars); doneReplace = true; visited[i] = true; res.add(i); if (stars == T.length) { break; } } } if (!doneReplace) { return new int[0]; } } int[] resArray = new int[res.size()]; for (int i = 0; i < res.size(); i++) { resArray[i] = res.get(res.size() - i - 1); } return resArray; } private boolean canReplace(char[] T, int p, char[] S) { //canReplace(char[] T, int p, char[] S) is used to check if any substring from Target is existing to be replaced with *. for (int i = 0; i < S.length; i++) { if (T[i + p] != '*' && T[i + p] != S[i]) { return false; } } return true; } private int doReplace(char[] T, int p, int len, int count) { //doReplace(char[] T, int p, int len, int count) is used to replace the substring with * and return the total number of * we have now. for (int i = 0; i < len; i++) { if (T[i + p] != '*') { T[i + p] = '*'; count++; } } return count; } }