1. All Permutations
Question: Write a recursive function that returns all permutations of a given string.
- For example, given “”, y should return [],
- For example, given “ho” should return [“ho”, “oh”],
- For example, given “hey” should return [“ehy”, “eyh”, “hey”, “hye”, “yeh”, “yhe”].
Hints:
- You can treat one character of the given string and call recursively to treat the remaining part,
- What are the primary cases to stop the recursion?
Solution:
func allPermutations(string: String) -> Set<String> {
// 1.
guard !string.isEmpty else { return Set<String>() }
guard string.count > 1 else { return Set<String>([string]) }
var result = Set<String>()
for i in 0..<string.count {
// 2.
let char = string[i]
let newString = string[0..<i] + string[i+1..<string.count]
let temp = allPermutations(string: newString)
// 3.
for subString in temp {
result.insert(String(char) + subString)
}
}
// 4.
return result
}Explanations:
1. As a recursive function, define first the base case (empty string or single character).
guard !string.isEmpty else { return Set<String>() }
guard string.count > 1 else { return Set<String>([string]) }2. Iterate over all characters, keep the character at index i and recurse on the rest of the string (given string without the character at index i).
for i in 0..<string.count {
let newString = string[0..<i] + string[i+1..<string.count]
let temp = allPermutations(string: newString)3. Add to the results the concatenation of the character at index i plus all permutations gave by the recursive call.
for subString in temp {
result.insert(String(char) + subString)
}4. Return the results.
return resultComplexity:
- Time Complexity: The number of permutations for n elements is n!, so the time complexity is O(n!).
- Space Complexity: The number of permutations for n elements is n!, so the space complexity is O(n!).
Test-cases:
public func testAllPermutations() {
assert(allPermutations(string: "").sorted() == [], "allPermutations 1 not equal")
assert(allPermutations(string: "ho").sorted() == ["ho", "oh"], "allPermutations 2 not equal")
assert(allPermutations(string: "hey").sorted() == ["ehy", "eyh", "hey", "hye", "yeh", "yhe"], "allPermutations 3 not equal")
}Follow-up:
You could try to do it using an iterative way.
<< More Interview Questions | Data Structures and Algorythms >>