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 加１。然后在把 String b 从硬盘里面load 进来，一次一个character, 然后去相应的bucket 里面counter - 1。最后再扫一遍buckets, 每个bucket 里面的counter 应该为０。
这样下来，space complexity 就是 26 * sizeof(long) = 26 * 8 byte = 208 byte = 0.2 kb, 远远能装下内存。
Read full article from Buttercola: Twitter: Anagram
No comments:
Post a Comment