Zenefits skype电面

yuanhsh

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

// String input (M)
// String pattern (N)

// # output

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

路和leetcode的minmum window substring相似。

mcry

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

biubiu

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

EchoO

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

biubiu

EchoO 发表于 2015-5-1 01:31
你的算法是如果S=abcdab, T = abc会返回2还是1？

好像是1？
cdab应该不是abc的anagram?

yuanhsh

mcry 发表于 2015-4-30 10:39
只是求种类数吗？substring一定是连续的吗？
如果是的话，比minmum window substring简单些，pattern大小 ...

是的，substring一定要连续

yyboyz

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

池大侠

写了两种方法第一种naive 第二种O(m)

def findanagram(string, pattern):
string_len = len(string)
pattern_len = len(pattern)
if string_len < pattern_len:
return 0
anagram = set()
window_len = len(pattern)
for i in range(string_len - pattern_len + 1):
#print string[i:i+pattern_len]
cur_string = string[i : i + pattern_len]
if sorted(cur_string) == sorted(pattern) and cur_string != pattern:
anagram.add(cur_string)
print anagram
return len(anagram)
print findanagram('aabacabc', 'abc')
def findanagramFast(string, pattern):
string_len = len(string)
pattern_len = count = len(pattern)
if string_len < pattern_len:
return 0
anagram = set()
window_len = len(pattern)
pattern_hash = {}
start = 0
for char in pattern:
pattern_hash[char] = pattern_hash.get(char, 0) + 1
pattern_hash2[char] = pattern_hash2.get(char, 0) + 1
for index, char in string:
if pattern_hash.get(char, 0):
pattern_hash2[char] -= 1
if pattern_hash[char] >= 0:
count -= 1
if count == 0:
while True:
if pattern_hash.get(char, 0):
if pattern_hash2[char] < 0:
pattern_hash2[char] += 1
else:
break
start += 1
if index - start + 1 == pattern_len and string[start : start + pattern_len] != pattern:
anagram.add(string[start : start + pattern_len])
return anagram
print findanagram('aabacabc', 'abc')

复制代码