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

实现如下函数:

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次。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,968评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,601评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,220评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,416评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,425评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,144评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,432评论 3 401
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,088评论 0 261
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,586评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,028评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,137评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,783评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,343评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,333评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,559评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,595评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,901评论 2 345

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,724评论 0 33
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,587评论 18 399
  • 有客户问:发票验旧如何做?今天就发票验旧那点事儿与大家聊聊,希望对菜鸟级别的有所帮助。 感谢阅读,随意打赏。
    深广创业家园阅读 357评论 0 0
  • 伪命题铸成了一个新的行业,教育培训行业。曾经的岁月无有一对一,无有奥数,照样出陈景润,照样茅以升。去年暑假我想带孩...
    醉饮春江水阅读 348评论 0 1