Thursday, January 21, 2016

Twitter: Anagram

Given two string a and b, determine if we can use characters in a to compose the string b, each character in string a can be used once and only once.

Understand the problem:
有点像Anagram的题目。不过问题可能是如果String a 和 b 都很大的话,无法Fit 到内存里面怎么办?

如果假设String a 和 b 都只是含有a - z 这样26 个字符的话,可以先建立一 long[26] 的 数组,然后从硬盘中把String a load进来,一次load 一个character, 然后在相应的bucket里面统计词频, i.e, counter 加1。然后在把 String b 从硬盘里面load 进来,一次一个character, 然后去相应的bucket 里面counter - 1。最后再扫一遍buckets, 每个bucket 里面的counter 应该为0。

这样下来,space complexity 就是 26 * sizeof(long) = 26 * 8 byte = 208 byte = 0.2 kb, 远远能装下内存。


No comments:

Post a Comment