CareerCup 9.2

Write a method to sort an array of strings so that all the anagrams are next to each other.

what are anagrams: A word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.

怎么没人做这个...

不太明白是什么意思。。。

parker0203 发表于 2012-8-3 04:31
不太明白是什么意思。。。

anagrams 就像2楼解释的那样

BinaryWitch 发表于 2012-8-3 04:34
anagrams 就像2楼解释的那样

就是先sort 每个string 然后再吧这些strings sort一下？

parker0203 发表于 2012-8-3 04:42
就是先sort 每个string 然后再吧这些strings sort一下？

差不多 只是把原 string 改变了 不过也好解决

可以给每个 string 加入一个 sort 之后的 string 当作关键字排 费空间
也可以写新的 comparator 每次复制整个 string 比较 sort 的结果 费时间

https://github.com/parker0203/careercup/blob/master/9_2.cpp

parker0203 发表于 2012-8-5 04:49
https://github.com/parker0203/careercup/blob/master/9_2.cpp

swap string 用各种指针引用都报错， 最后还是用库函数了， 注释里的swap请忽略

https://github.com/writecoffee/c ... blob/master/9.2.cpp


1. Solution 1: Sacrifice the Space
• For each string, record the appearence of the 26 letters and make pair. Do a quick sort.
• The record work is proportional to the size of each strings, namely O(m). And the compar-
ison for the record sets take constant time (thinking the maximum size of these 26 letters).
At last, the quick sort which takes O(n log n) timing dominates the total timing complexity.
• As for the space complexity, extra mapping set for each string consumes O(n).
2. Solution 2: Sacrifice the Timing
• Sort the string list in place, where we need to copy the strings, compare the anagrams every
time comparing each list item.
• For the sake of each comparison inside the outer quick sort loop, the total time complexity
is O(mn log n).
• Because we exploit temporary space for each comparison, the space complexity could be
considered O(1).



========PS===========
1. hard to modify a quicksort to a version which can sort with equivalent values.
2. overloading the comparator in C++ is a bit tricky for me.