【第三轮】6.16-6.22 CareerCup 1.3

【解题思路】
用双层for循环，并引入开关变量，对两个字符数组顺次比较，一旦有相同的，将被比的字符赋值为空字符，并break内循环, 继续比较下一个字母，若内层循环遍历后也没有相同的字母出现，则return false，外层循环完全遍历后，return true
【时间复杂度】

【空间复杂度】

【gist link】
https://gist.github.com/a8e5a772f91a7159824e.git

【解题思路】
check the string is empty or not, null or not, length is equal. Create an array to count how many times every char in the string s1 showed up using ASCII. Then, loop string s2, minus 1 for each char in s2 using ASCII too. If one string is a permutation of the other, all in the array will be 0.
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/UncleGarden/ee937ea3ffcebad6264f

【解题思路】
  看s1是不是s2的permutation:
    先建一个asccii的数组，记录s1中每个字符出现的次数；并减去s2中每个字符出现的次数
   最后遍历这个数组，看看是否每个字符的出现次数都为零
【时间复杂度】 o(n)
【空间复杂度】o(1)
【gist link】 https://gist.github.com/jaly50/da53a06f15bdbf720cdd
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】
compare string length, if different return false;
count character frequency, return a vector of integer;
compare character counts.
Improve: use only one vector to hold the counts, first add then substract, return false if a negative count occurs.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/19e3fa70461080d33475
【test case】
s1 = "", s2 = ""; return true
s1 = "", s2 = "1", return false


to楼上：不知道怎么在帖子里点评诶不过我在gist上给你review啦

readman 发表于 2014-6-16 00:21
【解题思路】
first loop add char to int array
second minus char in int array

空间复杂度为什么是O(1)？

不是利用了额外Int[]空间吗？

一直搞不清空间复杂度如何计算==

dreamhit 发表于 2014-6-17 06:06
Solution 1:
Sort the arrays, and compare the element one by one.
Time complexity O(nlogn)

为什么Solution1的space complexity是O(1)，而Solution2是O(n)，一直都不太会计算space complexity~~~

求解

zhenzhenanan 发表于 2014-6-17 06:46
【解题思路】
1. 建立一个int数组，初始化为全0，长度为ASCII字符种类（256）。
2. 遍历第一个字符串，记 ...

1. first to check whether the length of the two input string is equal is very important! Don't forget about it!
2. After Check the length of the two strings, there is no need to traverse the array again(the 3rd for loop), because if the two string have the same characters, and the count of a Key is not equal to 0 that means the two strings have different length!

fang_wu 发表于 2014-6-17 17:57
【解题思路】先把两个字符串转换为java 数组，然后排序，然后转换为string，用java来比较
【时间复杂度】O ...

Actually, you do not need to re-convert to string. because the equal function between two string is also a for loop statement to check each character.
But using the toString() method will create another two String type, because the string is immutable.

larry 发表于 2014-6-18 13:14
【解题思路】Use the thought we got in CC1.1
【时间复杂度】O(N)
【空间复杂度】O(1)

no need to use the 3rd for-loop actually (more detail you can look the 47 floor)

What's more, you can do some check in the second for-loop, and it will return false before traverse all the characters in the int[]

sanguine 发表于 2014-6-24 20:55
Actually, you do not need to re-convert to string. because the equal function between two string i ...

为啥我试过不行啊？如果不转换的话，只是一个数组，那么只会比较首地址，在java中的equal，只有转换为string