Permutations

Data Structures and Algorithms

Statement

Given an input string word, return all possible permutations of the string.

Constraints

• All characters in word are lowercase English characters
• All characters in word are unique
• 1 ≤ word.length() ≤ 6

Solution

"""
production algorithm
"""


class Solution:
    def find_permutations(self, word):
        """
        time complexity O(n * n!)
        space complexity O(n)
        """
        visited, current, result = set(), list(), list()
        self.find_permutations_helper(word, visited, current, result)
        return result

    def find_permutations_helper(self, word, visited, current, result):
        """
        time complexity O(n * n!)
        space complexity O(n)
        """
        if len(current) == len(word):
            result.append(str().join(current))
            return

        for i in range(len(word)):
            if word[i] in visited:
                continue
            visited.add(word[i])
            current.append(word[i])
            self.find_permutations_helper(word, visited, current, result)
            current.pop()
            visited.remove(word[i])

"""
unit tests
"""

from unittest import TestCase
from algorithms.subsets.permutations.solution import Solution


class SolutionTestCase(TestCase):
    def test_single_character_word(self):
        # Given
        word = "d"
        solution = Solution()

        # When
        actual = solution.find_permutations(word)

        # Then
        expected = ["d"]
        self.assertEqual(actual, expected)

    def test_multi_character_word(self):
        # Given
        word = "dog"
        solution = Solution()

        # When
        actual = solution.find_permutations(word)

        # Then
        expected = ["dog", "dgo", "odg", "ogd", "gdo", "god"]
        self.assertEqual(actual, expected)

Strategy

Subsets.

Explanation

Backtracking is used to find all permutations. For each step of recursion in backtracking, a character is appended to the end of the current permutation seen so far. If the character is already included in the permutation, then exclude adding it again. At the maximum recursion depth, i.e. when all characters have been included in the permutation, then copy and record the permutation.

Time Complexity

Given a word with n characters, there are n! permutations of the word. At the maximum recursion depth when a permutation has been found, then the permutation is copied and recorded, which has time complexity O(n). Therefore, the time complexity of the algorithm is O(n * n!).

Space Complexity

Due to recursion of backtracking, the call stack reaches a maximum depth of n. Also, the set of visited characters has a maximum size of n. Both of these components of the algorithm grow linearly. Therefore, the auxiliary space complexity of the algorithm is O(n).

Links

data_structures_algorithms/algorithms/subsets/permutations at main ·…