【第三轮】6.16-6.22 CareerCup 1.3

【解题思路】
First filter corner cases: null/empty/string with different length
Then creating a table with length of char set, which is used to track the frequency of characters presented in two strings.
add 1 freq for first string's chars and subtract 1 freq for second string's chars.
If two strings are permutation of each other, the frequency table should has 0 for all chars as a result.

【时间复杂度】
O(N) for traversing the string

【空间复杂度】
O(1) for unicode or ascii

【gist link】
https://gist.github.com/chrislukkk/10fb1cec3016a5ec8dcb

【test case】
check permutation of empty/null/string with different length/permuatations

【解题思路】Assume all chars are in ASCII. Create an array with length of 256. Traverse the first string to increase the number of existing chars. Traverse the second string to decrease the number of existing chars. If the number of a char is 0 before decreasing, return false. If nothing happens after traversing the second string, return true.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/ebe55c3d28fac5de37de

Neal 发表于 2014-6-19 07:48
【解题思路】Use a array of length 256 to record the count of each char in the string
【时间复杂度】 ...

赞之前check两个str是否一样，但是应该用equals还是==呢？

时间复杂度:O(n)
空间复杂度：　Ｏ（１）

gist : https://gist.github.com/daisyang/c72ba258d327580d3518

heycinderella 发表于 2014-6-20 00:16
赞之前check两个str是否一样，但是应该用equals还是==呢？

这里不是检查两个str一样，而是检查这两个引用是不是指向同一个str对象。比如isPermuation(str, str)或者isPermuation(null, null)这种情况的。如果用equals就是直接花O(n)的时间比较了，没什么意义

heycinderella 发表于 2014-6-20 00:16
赞之前check两个str是否一样，但是应该用equals还是==呢？

这里不是检查两个str一样，而是检查这两个引用是不是指向同一个str对象。比如isPermuation(str, str)或者isPermuation(null, null)这种情况的。如果用equals就是直接花O(n)的时间比较了，没什么意义

【解题思路】俩数组分别保存两个字符串中各个字符出现的次数（ascii），然后比较俩数组（Arrays.equals in util）相等的话返回true，不同的话返回false
【时间复杂度】o（n）
【空间复杂度】o（1）
【gist link】https://gist.github.com/weazord/0b9baf21fb5d25436726
【test case】

【解题思路】
assumption: String are based on ASCII. White spaces difference also counts.
Firstly, if two strings have different length, they are not permutation to each other. Then, if two string have exact same number of each character, they are permutation to each other.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/bloodbane/9b80c7887afc1411f81a

【解题思路】use dictionary
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】
https://gist.github.com/tangxukai/8e47209a30b3ac9ff99e
【test case】

【解题思路】
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】
https://gist.github.com/Tsien/a39a2edf6c4535eba329