Max Repeat Source to Construct Target - 1point3acres

可删除字母，需要多少次构造
http://massivealgorithms.blogspot.com/2018/05/leetcode-686-repeated-string-match.html
source和target，求问最少需要repeat source几次才可以得到target，repeat完的string可以删除任意character。先是暴力解然后优化的。

原作者 sakura328 先用window做的，但是没有记忆。后面优化是先遍历记录source里每个字母的所有位置在treeset，遍历target的时候记录当前字母在source的位置优化的，如果先用list记录用二分法，整体时间复杂度应该会更快一点，我主要是来不及就偷懒用treeset了。

https://www.1point3acres.com/bbs ... read&tid=463515

和 LIS 一个意思, 最坏情况O[mn], m = source string 长度, n = target string 长度 好一点的做法就是你这里说的. 这个解法算官方解答吗 https://techdevguide.withgoogle. ... -of-given-string/#!

你这题我应该是做过的。所以第一反应就比较像N+L。

但是我觉得和楼顶那题很像。只不过一个是连续走，而楼顶的题目是跳着走

用贪心的思想写了一个，我的理解是这里是subsequence，不是substring

    public int findRepeatingTimes(String target, String resource) {

        int indexInTarget = 0;

        int indexInResource = 0;

        int lent = target.length();

        int lenr = resource.length();

        while(indexInTarget < lent) {

            char c = target.charAt(indexInTarget);

            if(c == resource.charAt(indexInResource%lenr)) {

                indexInResource++;

                indexInTarget++;

            } else {

                indexInResource++;

            }

        }

        if(indexInResource%lenr == 0) return indexInResource/lenr;

        else return indexInResource/lenr + 1;

    }

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=463515&extra=&page=2

我先用window做的，但是没有记忆。后面优化是先遍历记录source里每个字母的所有位置在treeset，遍历target的时候记录当前字母在source的位置优化的，如果先用list记录用二分法，整体时间复杂度应该会更快一点，我主要是来不及就偷懒用treeset了。

厉害！这样你的复杂度就只有 O(N LogM)了。

达不到O(N lgM). 想一想当source 里有重复字符时。

worst应该是O(NM lgM).

全是重复字符的时候，即worst才是O(N logM).  楼主的做法是BS每个N中字符在该list里的位置。你再想想。

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=507548&page=1#pid6280126
source: ‘abc’
subsequences: a,b,c,ab,ac,bc,abc
target: ‘abcac’. From 1point 3acres bbs

Can the target string be constructed by concatenating the subsequences of the source string?
follow up: What is the minimum number of concatenations required?

第一问感觉判断一下是否出现source里没出现的词就行了吧。 反正每个字母都是一个subsequence

这跟word break那道题思路很像吧，只不过把wordDict换成了subsequence，用DP两层loop第一层遍历第二层backtracking找source[j:i+1]在不在subsequence里，在就update DP当前的最小值 DP[i+1] = min(DP[i+1], DP[j]+1)，最后返回DP[-1]这样子, 但是如果subsequence不是已知input的话要先去找出所有subsequence这又要费点事，应该还有更好的解法

def min_str(src, target):

    dic = collections.defaultdict(list)

    for i, s in enumerate(src):

        dic[s].append(i)

  

    res = 0

    i = 0

    n = len(target)

    while i < n:

        j = i

        tmp_dic = collections.defaultdict(int)

        prev = None

        while j < n:

            a = target[j]

            if a not in dic:

                return -1

            else:

                tmp_dic[a] += 1

                # case1: 若使用过的字符a数量 > dic里记录a的长度，则需要一个新的src, 对应Example 1

                # case2: 若当前字符a在src的index小于其前一个字符的index, 则也需要一个新的src，对应Example 2

                if tmp_dic[a] > len(dic[a]) or \

                        (prev is not None and dic[a][tmp_dic[a]-1] < prev):

                    break

                prev = dic[a][tmp_dic[a] - 1]

            j += 1

        res += 1

        i = j

    return res