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

use additional array to be ascii. space O(n) time O(n)

https://gist.github.com/njcongtou/4971300

Use two arrays to map each of two strings, other part is the same as others above.
https://github.com/moophis/careercup/blob/master/1.3.cpp

jimwallet 发表于 2013-2-17 20:28
use additional array to be ascii. space O(n) time O(n)

https://gist.github.com/njcongtou/4971300

What if a string with some characters in it occurred more than once?

jimwallet 发表于 2013-2-17 20:28
use additional array to be ascii. space O(n) time O(n)

https://gist.github.com/njcongtou/4971300

Correct me if I am wrong, I think it won't work since you have not taken number of occurance into account, your method would return true if you pass "abb" and "aab" into the method.

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

We could make some improvement by adding something like this at the very begining of the function, since there is no fun in comparing two strings with different length:
if(str1.size() == str2.size())
{
// your implementation
}
return false;

zuohr 发表于 2013-2-17 23:46
We could make some improvement by add something like this at the very begining of the function, si ...

You are right. I will update my program right now. Thank you!

zuohr 发表于 2013-2-17 23:39
Correct me if I am wrong, I think it won't work since you have not taken number of occurance into  ...

Thanks. You are right.
To handle that case, the occurance number in ascii array is increased by 1 when we iterate first string. the occurance number in ascii array is decreased by 1 when we iterate second string. Last, we iterate ascii array to check if all values are 0.

https://gist.github.com/njcongtou/4971300
o(n) space and time

1. both str must have same length
2. for same char, both str have same count

time complx O(n)

https://gist.github.com/mazl123321/4972623

jimwallet 发表于 2013-2-17 20:28
use additional array to be ascii. space O(n) time O(n)

https://gist.github.com/njcongtou/4971300

awesome solution!

https://gist.github.com/cqx83/4973207
思路，和1.1基本一样，需要新建array记录每个字符的个数比较是否相同。O(n)
已测试