【第三轮】8.3-8.9 CareerCup 9.5

9.5 Write a method to compute all permutations of a string

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

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

【解题思路】
Steinhaus-Johnson-Trotter algorithm: wiki
By alternating between descending and ascending placements of n, each permutation differs from the previous one either by the single-position-at-a-time motion of n, or by a change of two smaller numbers inherited from the previous sequence of shorter permutations.
【时间复杂度】
O(N!)
【空间复杂度】
O(N!)
【gist link】
https://gist.github.com/1b9a43cf2fa1f5a115eb

【解题思路】
The permutations containg all N characters are just to insert the n-th character to every spot of each permutation containing only previous (N-1) characters.

【时间复杂度】
O(n!)

【空间复杂度】
O(n!)

【gist link】
https://gist.github.com/happyWinner/c43d47111a2e4d410abc

【解题思路】
Similar as 9.4, but instead of tracking sets we are tacking permutations(order matters)

【时间复杂度】
O(N!)

【空间复杂度】
O(N!)

【gist link】
https://gist.github.com/chrislukkk/9edbe69c5223c05f1235

【解题思路】perm(n)= traverse(perm(n-1))
【时间复杂度】
O(N!)
【空间复杂度】
O(N!)
【gist link】
https://gist.github.com/bitcpf/7b398745558d3fd0a9de