hiho一下第84周《Lucky Substrings》题目分析

5
0

题目大意

给定一个只包含小写字母的字符串S

对于S的任意一个非空子串,若其包含的不同字母个数为fibonacci数列中的数,则我们认为这个子串为幸运的

请找出S的所有幸运的子串。

解题思路

一个简单的解题思路是直接枚举S的所有子串,并对其不同字母个数进行统计。

S均由小写字母组成,因此其包含的不同字母个数最多为26个。而在26以内且属于fibonacci数列的数为1,2,3,5,8,13,21。因此只有当子串中不同字母的个数为1,2,3,5,8,13,21时,该子串才是幸运的

接下来即是如何统计一个子串的不同字母个数,下面给出一种比较朴素的方法:

isLucky(subString):
    alphabet[] = false
    count = 0
    For c in subString
        If not alphabet[c] Then
            alphabet[c] = true
            count = count + 1
        End If
    End For
    Return (count is Fibonaccid number)

S的最大长度为 N = 100,该朴素算法的时间复杂度为O(N^3),是可以通过所有数据的。

同时,我们可以通过一个小的优化,将算法的时间复杂度减少的O(N^2)。

在已经知道S[i..j]字母个数的情况下,我们可以直接推导出S[i..j+1]的不同字母个数。

首先我们需要改进isLucky函数:

alphabet[] = false
count = 0
isLucky(c):
    If not alphabet[c] Then
        alphabet[c] = true
        count = count + 1
    End If
    Return (count is Fibonaccid number)

这里我们把alphabetcount从函数中抽取出来,作为了全局变量。同时,isLucky的参数变为单个字符,每次将新增的S[j+1]加入统计中。

下面是函数的主体部分:

For i = 0 .. len - 1
    alphabet[] = false
    count = 0
    For j = i .. len - 1
        // 此时isLucky返回的是S[i..j]的不同字母数量是否满足条件
        If isLucky(S[j]) Then
            ansList.push(S[i..j])
        End If
    End For
End For

最后只需要将ansList所保存的子串进行排序去重后输出,即可顺利通过该题目。

2 answer(s)

2

可以暴力枚举斐波那契数列中的数字,然后O(n)查找有几个子串符合条件……这个效率是O(n)的……

  • 这个算法不错。考虑到斐波那契数列是指数增长的,这个算法可以认为是O(nlogn)的?

  • 感觉这个想法有点问题:首先暴力枚举斐波那契数列时,是需要先计算出子串中有多少个不同的字符的,只要子串满足该特征,自然已经符合条件了。

  • 添加评论
  • reply
0

这题有O(n)的解法的吧……在n<=100的时候……

write answer 切换为英文 切换为中文


转发分享