阅读 33

Google面试题 | 循环字符串里面的独立子串

专栏 | 九章算法
网址 | www.jiuzhang.com

题目描述

假设s是一个无限循环的字符串”abcdefghijklmnopqrstuvwxyz”,s就是一个”...zabcdefghijklmnopqrstuvwxyza...”这样的字符串,现在给你另外一个字符串p,求p中存在多少个截然不同的子串,使得它们也是s的子串。p只包括英语的小写字母并且p的长度可能大于10000。

样例说明

输入:a
输出:1
说明:只有'a'是s的子串。

输入:cac
输出:2
说明:只有'a'和'c'是s的子串。

输入:zab
输出:6
说明:'z','a','b','za','ab','zab'都是s的子串。

解题思路

  1. 这一题我们首先考虑的是,一个长为n的连续的串,有多少个符合题目要求的子串呢?经过思考我们可以得出长为n的连续的串,我们有1+2+3+...+n这么多个符合题目要求的子串。

  2. 解决了上述这个问题,我们直接找出p中所有连续的子串的长度L1,L2,L3...Ln,我们若是直接对(1~L1)(1~L2)...(1~Ln)求和,我们得到的结果显然是错误的,因为会存在字符串重复的问题,例如abcdpjiezabc,这里abcd和zabc有一部分abc是重复的,我们要求有多少种不同的子串,就需要把这部分重复的减去。如果我们采用暴力计算的方法显然很麻烦,那么我们要如何才能避免计算到重复的呢?

  3. 在我们学过的数据结构中,有一种数据结构可以避免重复,那就是哈希表!
    在本问题中,我们也可以通过哈希表去重。对于一个符合条件的子串(符合条件指的是该串为p的子串),我们只需要记录“长度”和“结尾字符”这两个关键字就可以唯一确定这个子串。我们以abcdpjiezabc为例,两个符合条件的极大子串为abcd和zabc,对于abcd,我们把[1,a],[2,b],[3,c],[4,d]记录到哈希表。细心的读者可以发现,我们不需要记录[1,b],[2,c]等等,因为[2,b],[3,c]天然包含了长度比它们小的子串。对于zabc,我们记录[1,z],[2,a],[3,b][4,c]

  4. 得到哈希表之后,我们如何统计答案呢?
    我们发现,对于[1,a],因为哈希表中已经存在[2,a],所以[1,a]所表示的子串已经在[2,a]中被统计。也就是说,为了避免重复统计,我们只需要记录某个字母结尾的、长度最大的那个符合条件的子串长度就可以了。假设我们的哈希表中对应某个字母P的最长子串长度为k,因为长为k的字符串,有k个子串是以P结尾的,那么我们需要给最终答案加上k,这种统计方式把所有可能的子串都记录其中,并且不会重复。综上我们的算法时间复杂度为遍历数组和更新哈希表的时间复杂度:O(N),空间复杂度为O(1)。

参考代码

Unique Substrings In Wraparound String 参考代码

面试官角度

本题考察了字符串的基本操作,以及用哈希表去重的思想,难点在于把最开始的统计方式转变为以结尾字母为单位的统计方式,算是面试中中等难度的题目。给出正确算法可以达到hire。

Lintcode 字符串相关题目推荐

Substring Anagrams


推荐阅读



欢迎关注我的微信公众号:九章算法(ninechapter)。
精英程序员交流社区,定期发布面试题、面试技巧、求职信息等

九章算法,IT教育领域的深耕者
九章算法,IT教育领域的深耕者

关注下面的标签,发现更多相似文章
评论