Actually we dont need to use extra array to check whether a letter is used or not:
def permutations(l):
# WRITE YOUR BRILLIANT CODE HERE
if not l:
return []
res = []
permutation = []
def dfs(l, permutation, res):
if len(permutation) == len(l):
res.append(list(permutation))
return
for letter in l:
if letter not in permutation:
permutation.append(letter)
dfs(l, permutation, res)
permutation.pop()
dfs(l, permutation, res)
return res
if letter not in permutation: ⌠this line would be a problem when there are duplicate characters in âlâ
but checking if a letter in current permutation cost O(n) time, while checking a âusedâ flag is O(1)
@konnomiya - you are incurring a heavy cost of searching in an array (OlogN at best) when you do âif letter not in permutationâ. by keeping a set or a bitmap like the solution here it becomes O(1). actually there is a way to not have any state check - by swapping the elements in the input. check the LC solution: https://leetcode.com/problems/permutations/solution/
Compare âGet Itemâ to âx in sâ for list operations here: https://wiki.python.org/moin/TimeComplexity . Doing this will increase the time complexity of our code by adding this linear time execution inside an inner loop.
Hi mod, for the Python solution. The code outputs the right answer, just the formatting doesnât match the expected output.
The comment on line 9 may need to be updated. Isnât res appending a String not a List?
What is the Space Complexity of this solution?
The pass criteria could be updated to accept results emitted in a different order (see solution above).
The following code does the same thing but much more cleaner:
def permutations(letters: str) â List[str]:
res = []
def perm(let, cur_res):
nonlocal res
if len(let) == 0:
res.append(cur_res)
for i in range(len(let)):
perm(let[:i] + let[i+1:], cur_res + let[i])
perm(letters, "")
return res
Note that the solution currently expects the results to be sorted. I had to sort the list I created:
from typing import List
def permutations(letters: str) -> List[str]:
# WRITE YOUR BRILLIANT CODE HERE
results = set()
def backtrack(listed, startIndex):
results.add(''.join(listed))
if startIndex == len(letters):
return
for char in range(1, len(listed)):
listed[0], listed[char] = listed[char], listed[0]
backtrack(listed, startIndex + 1)
listed[char], listed[0] = listed[0], listed[char]
# swap letters
backtrack(list(letters), 0)
return sorted(list(results))
if __name__ == '__main__':
letters = input()
res = permutations(letters)
for line in res:
print(line)
C# Version with bitmasking
public static List<string> Permutations(string letters)
{
var res = new List<string>();
_permutations(letters, new System.Text.StringBuilder(letters.Length), 0, res);
return res;
}
public static void _permutations(string str, System.Text.StringBuilder prefix, int usedMask, List<string> res){
if (prefix.Length == str.Length){
res.Add(prefix.ToString());
return;
}
for (int i=0; i<str.Length; i++){
//Check if this bit is on for this index
if ( (usedMask & (1 << i) ) > 0 ){ continue; }
//Store the permutation so far (until it gets to max size and the next dfs will backtrack after storing it)
prefix.Append(str[i]);
//Turn on bit for index i for next dfs call so we don't process this letter again
//Use a new mask so we don't change the one associated with this current stack frame
int newMask = usedMask | (1 << i);
//Down we go
_permutations(str, prefix, newMask, res);
//Pull the last letter off now that we ran all the permutations with it ending the prefix sequence
prefix.Remove(prefix.Length-1,1);
}
}
/C++ Version/
void BuildTree(std::string letters, std::string path, std::vectorstd::string& stringVec)
{
for(int i = 0; i < letters.length(); ++i)
{
//Store letter for use in path
char aLetter = letters[i];
//Remove letter since used as part of the permutation
std::string lettersCopy = letters;
lettersCopy.erase(i,1);
if(lettersCopy.length() > 0)
{
BuildTree(lettersCopy, path + aLetter, stringVec);
}
else
{
stringVec.push_back(path + aLetter);
}
}
}
std::vectorstd::string permutations(std::string letters) {
std::vector<std::string> stringVec;
BuildTree(letters, "", stringVec);
return stringVec;
}
Weird format fix:
//Store letter for use in path
char aLetter = letters[i];
Still weird formatting: fixing againâŚ
char aLetter = letters[i]; //Store letter for use in path
Why does order matter in the tests?
Very clear explanation, I did some backtracking problems before, never realized it actually has a pattern. Thanks for summarizing.
Quick question I did it on a diferent compiler and it worck but when I try it here its not giving me the right answer
from typing import List
def permutations(letters: str) â List[str]:
listL=[]
bfs(letters.split(),listL,ââ)
return listL
def bfs(letters,listL,s):
if (len(letters)==0):
listL.append(s)
for x in letters:
s+=x
temp=letters[:]
temp.remove(x)
bfs(temp,listL,s)
s=""
return listL