Given an input string, word, return all possible permutations of the string.
Note: The order of permutations does not matter.
Constraints:
All characters in word are unique.
1≤ word.length ≤6
All characters in word are lowercase English letters.
Problems such as this one, where we need to find the combinations or permutations of a given string, are good examples to solve using the subsets pattern as it describes an efficient Depth-First Search (DFS) approach to handle all these problems.
Let’s discuss a few basics first. We know that n! is the number of permutations for a set of size n. Another obvious and important concept is that if we choose an element for the first position, then the total permutations of the remaining elements are (n−1)!.
For example, if we’re given the string “abcd” and we pick “a” as our first element, then for the remaining elements we have the following permutations:
Similarly, if we pick “b” as the first element, permute “acd”, and prepend each permutation with “b”, we can observe a pattern here as shown in the illustration above. That pattern tells us how to find all remaining permutations for each character in the given string.
We can do this recursively to find all permutations of substrings, such as “bcd”, “acd”, and so on. This implies that generating all possible permutations of the given string involves exploring different combinations of characters, which can be done efficiently using the subset technique. The key idea is to take one character of the given string at a time and find all the permutations that start with this chosen character. For this, imagine filling empty positions equal to the length of the string in the following manner: place the chosen character at the first position, then against this character, try all the remaining characters in the second position. Next, for each pair of characters in the first and second positions, try all the remaining characters in the third position. Keep doing this until we reach the last position to be filled. This process will allow us to systematically arrange each character in different positions and generate all possible permutations of the given string.
Here is a visual representation of all recursions for input string “bad”:
Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.
Let’s start with the simplest step—swapping the indexes of the input string. We create a function to swap ...
Given an input string, word, return all possible permutations of the string.
Note: The order of permutations does not matter.
Constraints:
All characters in word are unique.
1≤ word.length ≤6
All characters in word are lowercase English letters.
Problems such as this one, where we need to find the combinations or permutations of a given string, are good examples to solve using the subsets pattern as it describes an efficient Depth-First Search (DFS) approach to handle all these problems.
Let’s discuss a few basics first. We know that n! is the number of permutations for a set of size n. Another obvious and important concept is that if we choose an element for the first position, then the total permutations of the remaining elements are (n−1)!.
For example, if we’re given the string “abcd” and we pick “a” as our first element, then for the remaining elements we have the following permutations:
Similarly, if we pick “b” as the first element, permute “acd”, and prepend each permutation with “b”, we can observe a pattern here as shown in the illustration above. That pattern tells us how to find all remaining permutations for each character in the given string.
We can do this recursively to find all permutations of substrings, such as “bcd”, “acd”, and so on. This implies that generating all possible permutations of the given string involves exploring different combinations of characters, which can be done efficiently using the subset technique. The key idea is to take one character of the given string at a time and find all the permutations that start with this chosen character. For this, imagine filling empty positions equal to the length of the string in the following manner: place the chosen character at the first position, then against this character, try all the remaining characters in the second position. Next, for each pair of characters in the first and second positions, try all the remaining characters in the third position. Keep doing this until we reach the last position to be filled. This process will allow us to systematically arrange each character in different positions and generate all possible permutations of the given string.
Here is a visual representation of all recursions for input string “bad”:
Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.
Let’s start with the simplest step—swapping the indexes of the input string. We create a function to swap ...