【第三轮】6.16-6.22 CareerCup 1.3

【解题思路】
若两个字符串长度不同，则返回 false
设字符集为 ascii（256个），利用一个大小为256的 int 数组；
第一遍对 s 中所有字符遍历，将每个字符出现的次数计入数组；
第二遍对 t 中所有字符遍历，在数组中减去字符出现的次数，若减去后小于 0，则返回 false；
返回 true
【时间复杂度】
n
【空间复杂度】
1
【gist link】
https://gist.github.com/JoyceeLee/826c8c3ea2bdedfe9622

Solution 1:
Sort the arrays, and compare the element one by one.
Time complexity O(nlogn)
Space complexity O(1)

Solution 2:
Time complexity: O(n), Space complexity: O(n)

Code link:
https://gist.github.com/Jocelyn9/d288fd5e38e7313ebb65

【解题思路】
1. 建立一个int数组，初始化为全0，长度为ASCII字符种类（256）。
2. 遍历第一个字符串，记录每一个字符出现的次数。
3. 遍历第二个字符串，每遇到一个字符，就在数组的相应元素中减去一。
4. 遍历数组，如果每一个元素都是0，则返回true；否则返回false。
【时间复杂度】
O(m+n)，其中m和n分别是两个字符串的长度。
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-1_3-cc
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Assumptions : case sensitive     do not ignore white space
1.
【解题思路】
use a hashmap to count the frequency of  every chars in str1,   traverse str1, corresponding frequency - 1,  return false when the frequency is going to be negative
【时间复杂度】
O(n)
【空间复杂度】
O(1)
2.
【解题思路】
compare two  sorted char arrays   element by element  or  compare two strings generated from sorted char arrays
【时间复杂度】
O(nlogn)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/jyhjuzi/6a48769758a67ee2a7ae

【解题思路】用两个HashMap分别统计字符串里字符出现的频率，然后比较两个HashMap，频数不一致的话return false。对大小写敏感，对空格敏感。如果想对大小写不敏感，在统计前可以先将字符串全部toLowerCase()或者toUpperCase()，对空格不敏感，可以在统计完成后，判断频数时跳过blank character
【时间复杂度】O(n)
【空间复杂度】O(1) （如果不可以破坏原string，调用toLowerCase()或toUpperCase()就是O(n))
【gist link】https://gist.github.com/chouclee/0fb6ccc84d604d50a14e
【test case】a = "我为人人"; b = "人人为我";

【解题思路】先把两个字符串转换为java 数组，然后排序，然后转换为string，用java来比较
【时间复杂度】O(nlogn)
【空间复杂度】O(1)
【gist link】https://gist.github.com/qiangusc/d468e3ee938dd8f2a5e2

【解题思路】遍历第一个字符串，根据每一个字符的ascii码令int数组中相应的元素+1.遍历第二个字符串，根据每一个字符的ascii码令int数组中相应的元素-1. 最后遍历int数组是否全部为0即可
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/asdw3276/f9e259ebf504db026e7d

感谢所有给我code review的小伙伴

【解题思路】length s!=length t,false; s,t are empty, false; put s,t from array to string ,compare they are equal or not
【时间复杂度】O(nlogn)
【空间复杂度】O(1)
【gist link】https://gist.github.com/hilda8519/3fbd305943dab4addd62

【解题思路】loop over all chars in string1 and add one to the corresponding ascii array. do the same thing but minus one to string2. at the end, if all the ascii number have value 0, return true.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/pchong90/c2badf9e895b8fbf7ee4

【解题思路】Use the thought we got in CC1.1
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/larry-liu/c3ec4c9f7f5586864963