[第二轮] 2/18-2/24 CareerCup 1.3

Given two strings, write a method to decide if one is a permutation of the other.

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

overview:
1. sort both two strings (I guess complexity depends on which sorting algorithm you chose)
2. compare two sorted strings

https://gist.github.com/edussx/4970544

edussx 发表于 2013-2-17 15:31
overview:
1. sort both two strings (I guess complexity depends on which sorting algorithm you chose ...

This will work. And like the first one, we can have an algorithm runs in linear time by using bitmap again

edussx 发表于 2013-2-17 15:31
overview:
1. sort both two strings (I guess complexity depends on which sorting algorithm you chose ...

This will work. And like the first one, we can have an algorithm runs in linear time by using bitmap again

Because the ASCII is between 0 to 127, the number of characteristics in each string can be counted.
What's more, if two strings have the same number of every characteristic, one is a permutation of the other.

https://github.com/Tedatworking/ ... ster/20130217_3.cpp

Arthur2012 发表于 2013-2-17 17:21
Because the ASCII is between 0 to 127, the number of characteristics in each string can be counted. ...

I think this is better than the first algorithm on complexity.

ryancooper 发表于 2013-2-17 16:52
This will work. And like the first one, we can have an algorithm runs in linear time by using bitm ...

Sorry, I still do not know how to achieve linear time without other additional data structure in the first one. Do you have better ideas? Thank you!

Arthur2012 发表于 2013-2-17 17:32
Sorry, I still do not know how to achieve linear time without other additional data structure in t ...

By using an additional array a[0, max_charset_size - 1],  you can count every char in original array by add one on corresponding position at array a. And then you can just sort the array in linear time by output array a one by one, just keep output every element char(x) for a[x] times. This also called Bucket Sort.

That's my thought. But I think it needs some additional arrays.

Wow, thank you very much!

use bitmap mapping character to ASCII

https://gist.github.com/chrislukkk/4970901