s*******f
发帖数: 1114 | 1 This is O(n). Hard to explain, but i think it deserve to go through it with
your test case.
//zzzz码遍本版，回报本版zzzz
//在一个大串中查找和另外一个字符串是anagram的子串:
//GetAnagram("abcdbcsdaqdbahs", "scdcb") ==> "cdbcs"
string GetAnagram(const char *s, const char *sub){
int ls = strlen(s);
int lsub = strlen(sub);
if (ls < lsub || lsub < 1)
return "";
int mp[256];
memset(mp, 0, 256 * sizeof(int));
while (*sub){
++mp[*sub++];
}
const char *p = s;
int count = 0;
whil... 阅读全帖 |
|
n********5
发帖数: 323 | 2 一道面试题，是需要写一个函数getAnagram()
这个函数是定义在一个Class里面，这个Class还有一个函数addWord()，用来向这个类
加入任意
word。
我的思路是用hashtable，当add word的时候，把需要加入的word sort一遍，然后查找
hash，如
果已经存在，就是用linkedlist的方式，把新加的word link到最后。这样getAnagram(
)只需要遍
历一遍这个hashtable就可以知道当前输入的words 所有的Anagram。
如果考虑sort的时间复杂度是O(nlogn), hashtable的lookup是O(1)，这个getAnagram(
)函数的效
率是O(nlogn)，假设getAnagram()的pass in是需要查找的word。
这个思路还有什么其他办法可以优化的吗？或者还有其他思路吗？谢啦！ |
|
w****x
发帖数: 2483 | 3 在一个大串中查找和另外一个字符串是anagram的子串:
GetAnagram("abcdbcsdaqdbahs", "scdcb") ==> "cdbcs"
就是两个指针一前一后, 但是每次查找都要检查rec[256], 时间复杂度是256*O(n), 其
实还不如nlogn. 有其他简单的办法吗?? |
|
