String Permutation II

Given a string, find all permutations of it without duplicates.

Example

Given “abb”, return [“abb”, “bab”, “bba”].

Given “aabb”, return [“aabb”, “abab”, “baba”, “bbaa”, “abba”, “baab”].

Solution: 这道题如果给出的字符串如果有重复字符，所以问题就变成了去掉重复的问题，那么在求不同的排列，需要有额外的变量去纪录当前的元素访问情况。这道题跟Permutations II类似。

def DFS(s, result, current, isVisited):
    if len(current) == len(s):
        if current not in s:
            result.append(list(current))
        return
    for i in range(len(s)):
        if isVisited[i] == False:
           isVisited[i] = True
           current += s[i]
           self.DFS(s, result, current, isVisited)
           isVisited[i] = False
           del current[-1]
def permutations(s):
    result = []
    isVisited = [False] * len(s)
    self.DFS(s, result, '', isVisited)
    return result