h*****g
发帖数: 312 | 1 careercup 书上的答案对吗？
Finding if two string are anagrams of each other.
我认为
1.先判断string1 和 string2 长度是否相等
2.然后把string1 的所有字符 用个int[256]的数组过一遍，
3.最后根据string2的字符串，从头到尾，相应地减去int[256]的值，如果遇到int[x]=
=0了就说明不match。
这几步就足够了吧？没必有想书上弄得那么complex吧？
如果我的想法不对，请帮忙给我举一个counterexample.
多谢~ |
l******c
发帖数: 2555 | 2 the most important thing is what the interviewer expects.
if we have enough memory space, all the sorting algorithms are useless
]=
【在 h*****g 的大作中提到】
: careercup 书上的答案对吗？
: Finding if two string are anagrams of each other.
: 我认为
: 1.先判断string1 和 string2 长度是否相等
: 2.然后把string1 的所有字符 用个int[256]的数组过一遍，
: 3.最后根据string2的字符串，从头到尾，相应地减去int[256]的值，如果遇到int[x]=
: =0了就说明不match。
: 这几步就足够了吧？没必有想书上弄得那么complex吧？
: 如果我的想法不对，请帮忙给我举一个counterexample.
: 多谢~
|
l*****a
发帖数: 14598 | 3 他的答案不能迷信
你的第一步似乎也可以没有。。
]=
【在 h*****g 的大作中提到】
: careercup 书上的答案对吗？
: Finding if two string are anagrams of each other.
: 我认为
: 1.先判断string1 和 string2 长度是否相等
: 2.然后把string1 的所有字符 用个int[256]的数组过一遍，
: 3.最后根据string2的字符串，从头到尾，相应地减去int[256]的值，如果遇到int[x]=
: =0了就说明不match。
: 这几步就足够了吧？没必有想书上弄得那么complex吧？
: 如果我的想法不对，请帮忙给我举一个counterexample.
: 多谢~
|
f***g
发帖数: 214 | 4 按照楼主的思路，第一步必须有。
不然的话：aaa, aa会被误判。
对于楼主的方法，我觉得挺好。
想了半天也没有反例。学习了。
【在 l*****a 的大作中提到】
: 他的答案不能迷信
: 你的第一步似乎也可以没有。。
:
: ]=
|
h*****g
发帖数: 312 | 5 抱歉~
我看懂，能不能详细点？
多谢~
【在 l******c 的大作中提到】
: the most important thing is what the interviewer expects.
: if we have enough memory space, all the sorting algorithms are useless
:
: ]=
|
j***y
发帖数: 2074 | |
h**********d
发帖数: 4313 | 7 你这和书上的算法不是一样吗?
书上有检查unique charactor的个数, 可能会比你这个快 |
j***r
发帖数: 69 | 8 <> says: sort the two words to get signatures to compare
, time is O(n log n). Use less space than your method. And almost as fast as
yours O(n), since n is less than 20 generally. |
q*****9
发帖数: 85 | 9 你这不就把unique和complete给去掉了么，比书上的会慢，书上的是为什么比sort and
compare快的原因。
]=
【在 h*****g 的大作中提到】
: careercup 书上的答案对吗？
: Finding if two string are anagrams of each other.
: 我认为
: 1.先判断string1 和 string2 长度是否相等
: 2.然后把string1 的所有字符 用个int[256]的数组过一遍，
: 3.最后根据string2的字符串，从头到尾，相应地减去int[256]的值，如果遇到int[x]=
: =0了就说明不match。
: 这几步就足够了吧？没必有想书上弄得那么complex吧？
: 如果我的想法不对，请帮忙给我举一个counterexample.
: 多谢~
|
q*****9
发帖数: 85 | 10 不好意思，你的是对的。
and
【在 q*****9 的大作中提到】
: 你这不就把unique和complete给去掉了么，比书上的会慢，书上的是为什么比sort and
: compare快的原因。
:
: ]=
|
W**********r
发帖数: 8927 | 11 没看过这题，Google了一下，说这两个是Anagram：George Bush = He bugs Gore，一
个长度是11，一个是12，因为空格数不同，还有的有Single Quote的也算，比如：A
decimal point = I'm a dot in place；那这长度判断有啥用？
【在 f***g 的大作中提到】
: 按照楼主的思路，第一步必须有。
: 不然的话：aaa, aa会被误判。
: 对于楼主的方法，我觉得挺好。
: 想了半天也没有反例。学习了。
|
W**********r
发帖数: 8927 | 12 感觉这就是一个典型的用HashMap存出现数的问题啊，没有Order的问题，所以不用用什么LinkedHashMap。扫描一下第一个String，把新字符（空格和Single Quote滤掉）当Key，1当Value存进去，老字符（已经在HashMap里）的话，计数+1。然后扫描第二个，如果出现新字符，Return false，老字符的话记数-1 （计数是0的话从HashMap去除） ... 复杂度就是个O(n)。 |
P**********c
发帖数: 3417 | 13 嗯，我觉得你说的是对的。书上应该是忘了一开始判断了长度是否相等。照它后面的解
法一开始就不用判断长度了。因为unique char一样多，每个出现次数又一样，那必然
长度也是一样的。
]=
【在 h*****g 的大作中提到】
: careercup 书上的答案对吗？
: Finding if two string are anagrams of each other.
: 我认为
: 1.先判断string1 和 string2 长度是否相等
: 2.然后把string1 的所有字符 用个int[256]的数组过一遍，
: 3.最后根据string2的字符串，从头到尾，相应地减去int[256]的值，如果遇到int[x]=
: =0了就说明不match。
: 这几步就足够了吧？没必有想书上弄得那么complex吧？
: 如果我的想法不对，请帮忙给我举一个counterexample.
: 多谢~
|
P**********c
发帖数: 3417 | 14 主要书上一开始也判断了长度的。
【在 W**********r 的大作中提到】
: 没看过这题，Google了一下，说这两个是Anagram：George Bush = He bugs Gore，一
: 个长度是11，一个是12，因为空格数不同，还有的有Single Quote的也算，比如：A
: decimal point = I'm a dot in place；那这长度判断有啥用？
|
