2 posts tagged with "Backtracking"

class Solution:
    def letterCombinations(self, digits: str):
        LETTERS = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        letters = [LETTERS[i] for i in map(int, digits)]

        def backtracking(comb: str, i: int):
            if i == len(digits):
                yield comb
                return
            for char in letters[i]:
                yield from backtracking(comb + char, i + 1)

        yield from backtracking('', 0) if digits else []


class Solution1:
    def letterCombinations(self, digits: str) -> list[str]:
        result = []

        def backtracking(comb: str, letters: list[str]):
            if not letters:
                return result.append(comb)
            for char in letters[0]:
                backtracking(comb + char, letters[1:])

        LETTERS = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        backtracking('', [LETTERS[i] for i in map(int, digits)])
        return result if digits else []


class Solution2:
    def letterCombinations(self, digits: str) -> list[str]:
        LETTERS = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        letters = [LETTERS[i] for i in map(int, digits)]
        result = []

        def backtracking(comb: str, i: int):
            if i == len(digits):
                return result.append(comb)
            for char in letters[i]:
                backtracking(comb + char, i + 1)

        backtracking('', 0)
        return result if digits else []

class Solution:
    def subsets(self, nums: list[int]):
        result = [[]]
        for num in nums:
            result += [r + [num] for r in result]
        return result