g家电面

同问这题如何优化

hyliu0000 发表于 2016-9-15 00:02
你看到连续两个字了吗？

这个就是我14楼问的...不知道这个题的意思是找occurrence > k 的任意子串，还是循环至少k次的循环子串
如果是前者，那数一下char count就行了
如果是后者，我在10楼贴了另外一个思路

hxtang 发表于 2016-9-15 00:06
这个就是我14楼问的...不知道这个题的意思是找occurrence > k 的任意子串，还是循环至少k次的循环子串
...

如果是前者也不一定对吧。
比如 k＝2， abcab 和 abacb 返回的结果就应该是不一样的

william_gong 发表于 2016-9-15 00:11
如果是前者也不一定对吧。
比如 k＝2， abcab 和 abacb 返回的结果就应该是不一样的

如果是前者，两个不都是true吗？

hxtang 发表于 2016-9-15 00:17
如果是前者，两个不都是true吗？

abacb没有两个连续字串是一样的呀

william_gong 发表于 2016-9-15 00:19
abacb没有两个连续字串是一样的呀

"a"和"b"都是子串，虽然它们只有一个字母....

hxtang 发表于 2016-9-15 00:21
"a"和"b"都是子串，虽然它们只有一个字母....

不连续啊。。。

william_gong 发表于 2016-9-15 00:21
不连续啊。。。

我的第一种理解是子串自己连续就好了，这个包括单字符的子串，不同的occurrence之间完全没有关系，比如aba, k = 2，返回true。

不然就是第二种理解，所有的occurrence都是连在一起的，比如abab, k = 2, 返回true, 但是abcab就返回false.

hxtang 发表于 2016-9-15 00:28
我的第一种理解是子串自己连续就好了，这个包括单字符的子串，不同的occurrence之间完全没有关系，比如ab ...

看上去是第二种，
ebay考过一道类似的题目

aangel 发表于 2016-9-15 06:29
看上去是第二种，
ebay考过一道类似的题目

那就是10楼说的brute force O(n3)，可以优化成两层循环O(n2)。不知道有没有更快的。