l******n 发帖数: 1250 | 1 Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
本来还想偷懒,写个O(n2)的算法了事,结果直接被面试官叫停
后来被迫想O(n)算法,好在稀了糊涂地写出来了
我45分钟之内,就写了这一道题
看板上的其他兄弟,随便就是写两道题。 我估计不是挂掉了,就得再加面一轮。 |
p*********g 发帖数: 2998 | 2 请问你这个题最后的return的数据结构是什么, 是不是return 一个hashtable, key放
string(排过序的), value放一个arraylist放所有在这个组的string? |
l******n 发帖数: 1250 | 3 是一个bucket
{ { abcd, dcba}, {chip, ipch}, {ook}} |
m******3 发帖数: 346 | 4 是不是用把每个string sort,得到一个排过序的string作为key, 然后原来的string作
为value插入map,有什么要注意的地方么?
【在 l******n 的大作中提到】 : Given an array of strings, return all groups of strings that are anagrams. : Note: All inputs will be in lower-case. : 本来还想偷懒,写个O(n2)的算法了事,结果直接被面试官叫停 : 后来被迫想O(n)算法,好在稀了糊涂地写出来了 : 我45分钟之内,就写了这一道题 : 看板上的其他兄弟,随便就是写两道题。 我估计不是挂掉了,就得再加面一轮。
|
l******n 发帖数: 1250 | 5 "得到一个排过序的string作为key, 然后原来的string作为value插入map"
这样同一个key会有很多value |
x****m 发帖数: 1084 | 6 value is a vector
【在 l******n 的大作中提到】 : "得到一个排过序的string作为key, 然后原来的string作为value插入map" : 这样同一个key会有很多value
|
x*****n 发帖数: 195 | 7 sort每个string里的chars的方法,这个本事是nlogn的操作,n是string的平均长度。
如果是m个string要处理,那时间复杂度是mnlogn。这个是面试官希望的么?
【在 l******n 的大作中提到】 : Given an array of strings, return all groups of strings that are anagrams. : Note: All inputs will be in lower-case. : 本来还想偷懒,写个O(n2)的算法了事,结果直接被面试官叫停 : 后来被迫想O(n)算法,好在稀了糊涂地写出来了 : 我45分钟之内,就写了这一道题 : 看板上的其他兄弟,随便就是写两道题。 我估计不是挂掉了,就得再加面一轮。
|
r********3 发帖数: 24 | 8 这个是先给定两个string a1, string a2,先判断是否长度相等,如果相等用radix
sort, time 复杂度 O(n*k),
n 是a1 长度,k=26,假设只有26个小写字母得话。
然后以排好序的作为一个key,放到hashtable里, 这样应该是O(n)
【在 l******n 的大作中提到】 : Given an array of strings, return all groups of strings that are anagrams. : Note: All inputs will be in lower-case. : 本来还想偷懒,写个O(n2)的算法了事,结果直接被面试官叫停 : 后来被迫想O(n)算法,好在稀了糊涂地写出来了 : 我45分钟之内,就写了这一道题 : 看板上的其他兄弟,随便就是写两道题。 我估计不是挂掉了,就得再加面一轮。
|
r******d 发帖数: 308 | 9 好像可以不用string长度
思路
Step1 把每个string用radix 的思路转换一下。 例如babab可以转换成a2b3(a出现2次b
出现3次)
Step2 将所有string放到一个hush table里。key 是上步转换后的string.value是list
。如果有conflict 就插入list尾端
Step3 遍历一遍所有string 打印结果
【在 r********3 的大作中提到】 : 这个是先给定两个string a1, string a2,先判断是否长度相等,如果相等用radix : sort, time 复杂度 O(n*k), : n 是a1 长度,k=26,假设只有26个小写字母得话。 : 然后以排好序的作为一个key,放到hashtable里, 这样应该是O(n)
|
x***i 发帖数: 585 | 10 难道这不是 leetcode 100年前的原题吗? 咋突然领出来?
am i missing sth? |
|
|
z**********e 发帖数: 12 | |
x****u 发帖数: 12955 | 12
为什么要先sort,然后再做hash?先检测长度,不同则不是。长度相同就直接挨个比较
两个string的字母,一个从前向后,一个从后向前,任何时候有不同就证明不是,中断
循环。循环正常完毕就证明是anagram。
还有应该可以把其中一个string反过来存储。然后把两个string做一个XOR。结果不是0
的就不是。
【在 r********3 的大作中提到】 : 这个是先给定两个string a1, string a2,先判断是否长度相等,如果相等用radix : sort, time 复杂度 O(n*k), : n 是a1 长度,k=26,假设只有26个小写字母得话。 : 然后以排好序的作为一个key,放到hashtable里, 这样应该是O(n)
|
l******s 发帖数: 3045 | 13 anagram is in different logic of palindrome
【在 x****u 的大作中提到】 : : 为什么要先sort,然后再做hash?先检测长度,不同则不是。长度相同就直接挨个比较 : 两个string的字母,一个从前向后,一个从后向前,任何时候有不同就证明不是,中断 : 循环。循环正常完毕就证明是anagram。 : 还有应该可以把其中一个string反过来存储。然后把两个string做一个XOR。结果不是0 : 的就不是。
|
x****u 发帖数: 12955 | 14
啊。错成这样。脑子糊涂了。
不过,还是不用sort,假设字符是英文字母,就设两个个26单元的array。然后一个
string从前向后,另一个sting从后向前,见到一个字符就把对应的那个array单元加一
。最后然后比较两个array,每个单元的数字都一样的就是anagram/
【在 l******s 的大作中提到】 : anagram is in different logic of palindrome
|
s******x 发帖数: 417 | 15 直接sort,然后查找Map,找到了就把index存入map,
然后回头再把map内index array个数多于1个的打印出来即可。
O(n) |
q*z 发帖数: 13362 | 16 应该可以design一个hash,把所有的anagram map到一个值上,这样就是o(n).
比如把字符视为27进制的数,a为1,z为26,先sort再转换,这样的hash应该是所有的
anagram map到同一个值的
hash计算可以从a到z扫描26遍,逐个进位。复杂度o(k)k为字符串长度。
注意hash变量的最大值会限制能处理的字串最大长度。
【在 l******n 的大作中提到】 : Given an array of strings, return all groups of strings that are anagrams. : Note: All inputs will be in lower-case. : 本来还想偷懒,写个O(n2)的算法了事,结果直接被面试官叫停 : 后来被迫想O(n)算法,好在稀了糊涂地写出来了 : 我45分钟之内,就写了这一道题 : 看板上的其他兄弟,随便就是写两道题。 我估计不是挂掉了,就得再加面一轮。
|
J*******o 发帖数: 741 | 17
同问, 面试官是不是不满意这种复杂度的?
【在 x*****n 的大作中提到】 : sort每个string里的chars的方法,这个本事是nlogn的操作,n是string的平均长度。 : 如果是m个string要处理,那时间复杂度是mnlogn。这个是面试官希望的么?
|
a******g 发帖数: 13519 | 18 不能是o(n)吧?sort的复杂度是多少?
【在 s******x 的大作中提到】 : 直接sort,然后查找Map,找到了就把index存入map, : 然后回头再把map内index array个数多于1个的打印出来即可。 : O(n)
|
j**********3 发帖数: 3211 | 19 我都没看懂这个题什么意思,和leetcode上有什么不同? |
n******n 发帖数: 12088 | 20 还有字符串本身长度。
【在 l******n 的大作中提到】 : Given an array of strings, return all groups of strings that are anagrams. : Note: All inputs will be in lower-case. : 本来还想偷懒,写个O(n2)的算法了事,结果直接被面试官叫停 : 后来被迫想O(n)算法,好在稀了糊涂地写出来了 : 我45分钟之内,就写了这一道题 : 看板上的其他兄弟,随便就是写两道题。 我估计不是挂掉了,就得再加面一轮。
|
s******x 发帖数: 417 | 21 pre-process不算复杂度。
查找的复杂度是O(n).
【在 a******g 的大作中提到】 : 不能是o(n)吧?sort的复杂度是多少?
|