【第三轮】6.16-6.22 CareerCup 1.3

【解题思路】
用一个128个变量的数组统计每个ASCII在第一个字符串中出现次数
遍历第二个字符串，遇到一个字符，就从数组相应位置中剪掉1
遍历数组。如果有不为0的数，表示两个字符串有不同的字符频次
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/d996c84e126d0d38fcde.git
测试用例选的 哈利波特里面 伏地魔 和汤姆·马沃罗·里德尔互换  ^_^

sanguine 发表于 2014-6-25 10:52
1.4里的题目写的是if implementing in Java, please use a character array so that you can perform thi ...

1.4的题目我也不确定它说的那个Java到底什么意思。

chouclee 发表于 2014-6-25 15:34
1.4的题目我也不确定它说的那个Java到底什么意思。

他的意思其实输入的时候要求是Char[]，否则不可能O(1)的space complexity解决

你可以输入string，但是函数参数必须char[]

solution 1
store the 1st string into a HashMap, the character as the key, the frequency as the value, and then traverse each character in the 2nd string
1. if there is a character doesn’t appear in the Key, return false
2. if existed, check the frequency of this Character, if count<0, return false, otherwise: count–
Time Complexity: O(n)
Space Complexity: O(n)

solution 2
Assume all the input characters are ASCII, initial a int[256] to track the frequency of each character
1. store the character into a int[], and the value is the frequency of the character
2. traverse the 2nd string, check just like the PermutationStringOne method.
Time Complexity: O(n)
Space Complexity: O(1)

solution 3
The solution 3 is slower than the two solution above.
1. convert string type into char[], using Arrays.sort() to sort the two char[]
2. check each item in the two char[](char1 == char2[i]), if not equal, return false

The Time Complexity is depend on the Sort method.
Arrays.sort() is using the QuickSort to implement sort, so the general time complexity is O(nlogn), the worst is O(n^2)

link is here: http://www.jyuan92.com/post-287
[/i]

【解题思路】
put each character of one string in a defined length array
and then remove same characters from the other string
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】
https://gist.github.com/JoshuaTang/58abeb3a69b7d0816734

【解题思路】The main idea is to use HashMap to record the apperance of each character in one string and use the other one to compare, if one character is not contained return false, else minus the correspond number.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】
https://gist.github.com/2d8a46704ae58bcf95ce.git
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
("".""), ("BABBA", "BAABA"), ("ABD", "ABC")

I found the code could be even simpler, the check of map's size is not necessary, since according to the drawer principle, if two string do not match, it would return false in the loop and the check of map's size would never take place of.

【解题思路】
check whether the input two strings equals null and whether they have the same length;
use a array to calculate the appearances of letters from the first string;
traverse the second string, if the appearances of its letter equal zero, return false; otherwise, minus the appearances by one.

【时间复杂度】O(n)


【空间复杂度】
O(1)


【gist link】
https://gist.github.com/happyWinner/966edca19c8c1e4b45c8

【test case】
input string is NULL