原题
给出一个字符串，找到它的所有排列，注意同一个字符串不要打印两次。
样例
给出 "abb"，返回 ["abb", "bab", "bba"]。
给出 "aabb"，返回["aabb", "abab", "baba", "bbaa", "abba", "baab"]。
解题思路
思路跟 Permutation II 完全一样
# -*- coding: utf-8 -*-
'''
给出一个字符串，找到它的所有排列，注意同一个字符串不要打印两次。
样例
给出 "abb"，返回 ["abb", "bab", "bba"]。
给出 "aabb"，返回["aabb", "abab", "baba", "bbaa", "abba", "baab"]。
解题思路
思路跟 Permutation II 完全一样
'''
class Solution:
# @param {string} str a string
# @return {string[]} all permutations
def stringPermutation2(self, strs):
# Write your code here
if strs is None:
return []
res = []
flags = [False] * len(strs)
self.helper(sorted(strs), flags, "", res)
return res
def helper(self, strs, flags, path, result):
if len(path) == len(strs):
result.append(path)
return
for i in range(len(strs)):
if not flags[i]:
if i != 0 and not flags[i - 1] and strs[i] == strs[i - 1]:
continue
flags[i] = True
self.helper(strs, flags, path + strs[i], result)
flags[i] = False
if __name__ == '__main__':
sol = Solution()
res = sol.stringPermutation2(strs='abc')
print(res)输出：['abc', 'acb', 'bac', 'bca', 'cab', 'cba']