【第三轮】6.16-6.22 CareerCup 1.3

【解题思路】统计两个字符串的字符出现次数，统计结果相同则permutation is true.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/guchang/9ba132f3a99399078a74

【解题思路】If the length of the strings are different, retrun false. Assume all char in the strings are ASCII, use 2 int arrays to store the number of chars in each string, then do a subtraction of the arrays, if all of the elements are 0, it is true.
Actually could be solved by Hash...
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/bitcpf/bc83a56c7c3ef44187cb

【解题思路】Assuming all the characters are from ASCii. First, we should judge if the lengths of two string are the same. Then we can use an array to store the times of appearing of one character in the first string. Then we subtract the number of responding position of the array recording to the second string if it has the same character.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/ZhuGuanyu/9f9f2d1bb3e38cfcc373

【解题思路】use an counter[256] (for extended ASCII), iterate str1 and str2, convert char into int as index of counter: for str1, ++counter[index]; for str2, --counter[index]. return false if found counter[i] is not equal to 0, else return true
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/xun-gong/6f344017108913a9ec8c

【解题思路】字符串先转换成列表，比较长度。 长度一样，再把每个字符转换成ASCII码
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/yokiy/23cfde3e7d270be30e2b

【解题思路】Use a array of length 256 to record the count of each char in the string
【时间复杂度】O(N)
【空间复杂度】O(1)
https://gist.github.com/nealhu/07e151dcbf188516af42

【解题思路】
/**
         * Assume the string falls under a certain encoding. Use an extra constant
         * size array of integers to store the frequency of each character in str1,
         * for each character in str2, minus the frequency array's value by 1. In
         * the end, check if each element in the frequency array is 0, if not then
         * str1 is not a permutation of str2.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/XiaoxiaoLi/4846b24cf7adfb5d4053

【解题思路】刚开始想到的还是 O(n^2)的，然后看了一下，貌似用周一的hash table的解法，O(n)就可以实现
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/sddxhwj/99314e73d8d2c4d289bb