import string
letters = string.ascii_lowercase
CHARACTER_HASH = dict(zip(letters, [0]*len(letters)))
def mapLettersToHash(text_a):
for char in text_a:
if char in CHARACTER_HASH.keys():
CHARACTER_HASH[char]+=1
def computeCommonLetters(text_b):
common_letters = 0
for char in text_b:
if CHARACTER_HASH[char] > 0:
common_letters+=1
return common_letters
def computeUncommonLetters(text_a, text_b, common_letters):
return len(text_a)+len(text_b)-(2*common_letters)
text_1 = "hello"
text_2 = "billion"
mapLettersToHash(text_1)
common = computeCommonLetters(text_2)
result = computeUncommonLetters(text_1, text_2, common)
print(result)
问题:给定两个大小为m和n的字符串,我们必须找出需要从这两个字符串中删除多少字符,以便它们成为彼此的anagram
我试图计算我的程序的空间和时间复杂性。 根据我的扣除:
创建字符哈希需要固定的时间和空间
接下来,映射文本的字符(如果大小是m)将花费O(m)
时间
接下来,从文本b(如果大小为n)计算公共字符将花费O(n)
时间
计算不常见字符是一个简单的算术运算,因此需要固定的时间。
因此,我的最终课程将有:
时间复杂度:O(m+n)
空间复杂度:O(1){由于字符散列}
如果我错过了什么,请告诉我?谢谢
目前没有回答
相关问题 更多 >
编程相关推荐