Google OA题目：给出使得字符串B成为字符串A重复自己构成的字符串的子字符串，字符串A最少需重复的次数

小灰灰 2022-06-08 02:19 42阅读 0赞

> 实现如下函数：
> 
>     class Solution {public int soluition(String A, String B); }
> 
> 其应当满足的功能为：给定包含N个字母的string A和包含M个字母的string B，返回使得B成为其子字符串A需> 要重复自己的最少次数。如果无论A重复自己多少次B都无法成为其子字符串，返回-1。  
> 如下面例子所示：
> 
>     A = "abcd"
>     B = "cdabcdab"
> 
> 这种情况下该函数需要返回3，因为A重复3次后成为\`”abcdabcdabcd”，此时B是该字符串的子串。  
> 本题假定：  
> N是\[1…1000\]内的整数。  
> M是\[1…1000\]内的整数。

### 思路分析 ###

给定两个string A和B，当B的长度大于A时，即使在brute-force解法的情况下（既不断重复A，看B能够成为当前字符串的子串），我们仍然首先要确定的是B究竟能够成为A重复自己所构造的字符串的子串。因为这决定了这个循环的结束条件。

注意到B如果能够由A不断重复自己得到，那么B中的任何和A的长度相等的连续子字符串都必须能够由A的rotation得到。例如上面的A和B的例子中，从B中取出任何一个长度为4的连续子字符串，都能够由A的rotation产生。所以我们只需要产生A的所有rotation并将它们存入HashSet中，然后再遍历一遍B中的所有长度与A相同的连续子字符串，就可以知道B能够由A重复自己产生。这一步骤的时间复杂度为：`O(N + M)`，空间复杂度为`O(N ^ 2)`。

`O(N + M)`时间复杂度：因为我们需要分别遍历A的所有rotation和B的所有长度与A相同的连续子字符串，分别是N种可能和M中可能，所以是`O(N + M)`。

`O(N ^ 2)`空间复杂度：因为我们需要存储所有A的rotation，一共是N种，而每一种包括N个字母，所以总空间为`O(N ^ 2)`。

当我们确定了B一定能由A不断重复自己得到之后，我们就只需要确定A最少需重复几次。这一步骤当然可以通过不断让A重复自己并判断B是否是当前字符串的子字符串实现。但这一方法并不是最优解。实际上考虑到B一定是A的rotation组成的，A的最少重复次数可以在`O(1)`时间，`O(1)`空间内实现， 方法如下：

1.  用HashMap而非HashSet来存储A的rotation。其中Key为A的rotation，Value为A成为当前rotation所需要的向左滚动的步数。例如上面的例子中的A，其所构造出的HashMap为：

{
        "abcd": 0,
        "bcda": 1,
        "cdab": 2,
        "dabc": 3,
    }

这样的情况下我们只需要判断B中的第一个长度与A相同的连续子字符串的rotation步数即可。

如果为0，则代表A只需要重复到（设A重复自己组成的字符串为A’）`A'.length() >= B.length()`即可，既重复`B.length() / A.length()`向上取整次，也就是：`B.length() / A.length() + (B.length() % A.length() == 0 ? 0 : 1)`。

如果不为0，则代表除去需要重复上面的次数之外，还需要额外的一次重复来满足c的开头部分。如上面的例子中：A重复两次即可满足上面的第一个条件。但这个时候B的开头的`"cd"`并没有成为子串，所以需要额外重复一次满足B的开头。也就是三次。也就是重复次数为：`1 + B.length() / A.length() + (B.length() % A.length() == 0 ? 0 : 1)`。

**需要注意的是，我们以上所有的讨论基于B的长度大于A的情况进行。如果B的长度小于A，我们只需要直接判断B是否为A的子字符串即可。这个判断可以通过KMP算法进行，从而将时间控制在`O(N)`内**。

以上算法的代码如下：

public class Solution {
        /**
         * Given 2 string A and B, return the minimum number A need to repeat itself in order
         * for B to become a substring of the repeated sequence of A.
         * 
         * In order for B to be able to become a substring of A's repeat, every B's substring
         * with the same length of A need to satisfy the requirement that it can be generated
         * through A's rotation. For example, A = "abcd" and B = "cdabcdab", every of B's substring
         * need to some rotations of A, e.g. "bcda", "cdab", "dabc", "abcd". 
         * 
         * If such a requirement is not satisfied, then -1 is returned to indicate that B cannot be obtained
         * through A's repeating itself. 
         * 
         * Otherwise, the minimum number of repeat needed for A is calculated as following:
         * 1. If B shares the same start pattern as A, ceil devision of B's length to A's length
         * is the minimum number of repeat needed.
         * 2. If B starts from some middle point character with A, then the minimum number of repeat
         * needed is the ceil devision of B's length to A's length plus 1. 
         */
        public static int minimumNumberRepeat(String A, String B) {
            // If A contains no character, then B cannot be obtained
            // by repeating A
            if (A == null || A.length() == 0) {
                return -1;
            }
    
            // If A is longer than B, search for B in A directly.
            if (A.length() > B.length()) {
                // repeat at most once to deal with condition like this:
                // A = "abcd", B = "da"
                for (int i = 0; i < 2; i++) {
                    String curr = new String(new char[i + 1]).replaceAll("\0", A);
                    if (curr.contains(B)) {
                        return i + 1;
                    }
                }
                return -1;
            }
    
            HashMap<String, Integer> permutationsA = new HashMap<String, Integer>();
            permutationsA.put(A, 0);
            for (int i = 0; i < A.length() - 1; i++) {
                String permutationA = A.substring(i + 1, A.length()) + A.substring(0, i + 1);
                permutationsA.put(permutationA, i + 1);
            }
    
            // Check if any substring of B cannot be generated by A's permutation
            for (int i = 0; i <= B.length() - A.length(); i++) {
                String subB = B.substring(i, i + A.length());
                if (!permutationsA.containsKey(subB)) {
                    return -1;
                }
            }
    
            // If every substring of B can be generated by A's permutation
            int rotation = permutationsA.get(B.substring(0, A.length()));
            if (rotation == 0) {
                return B.length() / A.length() + (B.length() % A.length() == 0 ? 0 : 1);
            } else {
                return 1 + B.length() / A.length() +  (B.length() % A.length() == 0 ? 0 : 1);
            }
        }
    }

### 进一步的思考 ###

注意到经过上面的分析，我们知道不论在何种情况下，A最多只需重复`1 + B.length() / A.length() + (B.length() % A.length() == 0 ? 0 : 1)`我们就可以判断出B是否能成为A不断重复自己构成的字符串的子串。所以我们只需要使用`for`循环检查这么多次即可。这种方法`for`循环的时间复杂度为`O((M/N) * N) = O(M)`。`for`循环中检查B是否为当前字符串的子串可以用KMP算法实现worst case为`O((M/N) * N) = O(M)`。所以算法的时间复杂度为`O(M ^ 2)`。算法空间复杂度为`O(M)`因为我们最坏情况下只需要存储一个长度大于等于`M`但小于`M+N`的字符串。

这种算法虽然时间复杂度上不如之前的算法，但胜在实现简单不用处理太多的特殊情况。

算法的具体实现如下：

public class Solution {
        public static int repeat(String A, String B) {
            // If A contains no character, then B cannot be obtained
            // by repeating A
            if (A == null || A.length() == 0) {
                return -1;
            }
    
            int totalTimes = 1 + B.length() / A.length() +  (B.length() % A.length() == 0 ? 0 : 1);
            for (int i = 0; i < totalTimes; i++) {
                String repeated = new String(new char[i + 1]).replaceAll("\0", A);
                if (repeated.contains(B)) {
                    return i + 1;
                }
            }
            return -1;
        }
    }

这里可能需要说明的一点是上面我用来重复A所使用的代码：`String repeated = new String(new char[n]).replaceAll("\0", A)`。其中`n`是我们想要重复A的次数。这段代码的工作原理是这样的：

首先我们用`char[n]`初始化了一个String。由于在这个`char[n]`数组中我们没有给出任何初始值，所以生成的String中的每一个字符的值都为`null`，其中共有n个字符。接下来我们用`replaceAll(regex, value)`这个方法匹配所有的`null`，也就是`"\0"`并将它们都替换为A，因此也就将A重复了n次。