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
Last updated
Was this helpful?