【第三轮】6.16-6.22 CareerCup 1.3

1.3 Given two strings, write a method to decide if one is a permutation of the other.

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

答案里面那个碰到 less than 0 就直接 break return false的小trick 真是聪明= =!

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]

【解题思路】
first loop add char to int array
second minus char in int array
third test chars  
【时间复杂度】
n
【空间复杂度】
n
【gist link】
https://gist.github.com/gaoyike/2839135b288b36d984e8
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【Some Question】
   1. Range of character. ASCII? 26 letters?
   2. can we destory the string?
   3. uppercase/lowercase. "dog" and "God" are anagram or not?
   4. blank space is ignored or not? "d" and "d    " are anagram or not?
【解题思路】
1. assign two arrays, each array store the numbers of every characters in the each string.
2. To optimize the method above, we can use just one array. Since we count the numbers of each characters in the first string, then we decrease them according the second string.
3. If the string can be destroyed, we can sort them first, then compare them.
【时间复杂度】
1. O(n)
2. O(n)
3. O(nlogn)
【空间复杂度】
1. O(1)
2. O(1)
3. O(1)
【gist link】
https://gist.github.com/qianhuang/1eeddb16121a0c0e0ed0

【解题思路】
  If the length of two strings are different, return False
  Put all characters from the first string into an array,
  Remove character which matches the character in the second string from the array
  If array is empty after the loop, return True
【时间复杂度】
  O(N)
【空间复杂度】
  O(1)
【gist link】
  https://gist.github.com/habina/19a729085f14c9d2a3bc
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
  Empty string

【解题思路】two int arrays are used to count each character for the given two strings, check if two counters for the same character mismatch
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/startupjing/3f4d8a9409d230992a6b
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】user interaction is implemented in the code

【解题思路】
use a dict(hashmap) to count the appearance of characters of the first string, then minus the number of that in the other string.
once the hash value is less than zero, return false
【时间复杂度】
O(n)
【空间复杂度】
O(1) for certain set of characters, say ascii
【gist link】
https://gist.github.com/monkerek/bd54cffd22ebde390a21

【解题思路】
1. compare the length of two strings, if not the same, return false; else go to 2
2. Use a hashmap to store the element & occurrences of chars in one string
3. Compare the other string with the hashmap, if cannot find a record of a char, break & return false; else minus the occurrence count, then go to 4
4. if all the occurrence counts are zero, return true, they are mutual permulations
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://github.com/FinalF/Carrer ... rmutationCheck.java

【解题思路】
Hash，must meet the prerequisites that: 1. not null 2. two string should be in equal length.Count the number of occurrence of characters in the first string, and minus the occurrence of characters in the second string. If count[c] < 0, return false.
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/21b1b1dd680f33d5ead7

【解题思路】
1. For 2 strings of same length, use a hashmap to store every character in s1, then check if those of s2 are contained in this hashmap.
2. Sort the 2 strings and compare their character in same index.
【时间复杂度】
1. O(n) for traversing char array. PS: containsKey() method has a time complexity of O(1).
2. O(nlg) for sorting.
【空间复杂度】
1. O(1) for hashmap.
2. O(1) if the strings are breakable.
【gist link】https://gist.github.com/6dfa93c2cc873f6f76e4.git
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
s1: "" s2: ""
s1: null, s2:"1111"