Skip to content

Backtracking Partition

Table of Contents

131. Palindrome Partitioning

131. Palindrome Partitioning - Python Solution
from typing import List


# Backtracking
def partition(s: str) -> List[List[str]]:
    n = len(s)
    res, path = [], []

    def dfs(start):
        if start == n:
            res.append(path.copy())
            return

        for end in range(start, n):
            cur = s[start : end + 1]
            if cur == cur[::-1]:
                path.append(cur)
                dfs(end + 1)
                path.pop()

    dfs(0)

    return res


if __name__ == "__main__":
    print(partition("aab"))
    # [['a', 'a', 'b'], ['aa', 'b']]

2698. Find the Punishment Number of an Integer

1593. Split a String Into the Max Number of Unique Substrings

1849. Splitting a String Into Descending Consecutive Values

306. Additive Number

842. Split Array into Fibonacci Sequence

93. Restore IP Addresses

93. Restore IP Addresses - Python Solution
from typing import List


def restoreIpAddresses(s: str) -> List[str]:
    result = []

    def backtracking(start_index, point_num, current, result):
        # stop condition
        if point_num == 3:
            if is_valid(s, start_index, len(s) - 1):
                current += s[start_index:]
                result.append(current)
            return

        for i in range(start_index, len(s)):
            if is_valid(s, start_index, i):
                sub = s[start_index : i + 1]
                backtracking(i + 1, point_num + 1, current + sub + ".", result)
            else:
                break

    def is_valid(s, start, end):
        if start > end:
            return False

        if s[start] == "0" and start != end:
            return False

        num = 0
        for i in range(start, end + 1):
            if not s[i].isdigit():
                return False
            num = num * 10 + int(s[i])
            if num > 255:
                return False
        return True

    backtracking(0, 0, "", result)

    return result


print(restoreIpAddresses("25525511135"))
# ['255.255.11.135', '255.255.111.35']

816. Ambiguous Coordinates

140. Word Break II

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, hash table, string, dynamic programming, backtracking, trie, memoization

291. Word Pattern II

Comments