Leetcode 题解 - 回溯-分割

1. 分割回文串1

  1. Palindrome Partitioning (Medium)

Leetcode / 力扣

  1. # 递归
  2. def partition(self, s: str) -> List[List[str]]:
  3.     def backtrack(s, path_tmp):
  4.         if not s:
  5.             res.append(path_tmp)
  6.             return
  7.         for i in range(1, len(s) + 1):
  8.             if s[:i] == s[:i][::-1]:
  9.                 backtrack(s[i:], path_tmp + [s[:i]])
  11.     res = []
  12.     backtrack(s, [])
  13.     return res

2. 复原IP地址

  1. Restore IP Addresses (Medium)

Leetcode / 力扣

  1. # 递归
  2. def restoreIpAddresses(self, s: str) -> List[str]:
  3.     res = []
  4.     n = len(s)
  6.     def backtrack(i, tmp, flag):
  7.         if i == n and flag == 0:
  8.             res.append(tmp[:-1])
  9.             return
  10.         if flag < 0:
  11.             return
  12.         for j in range(i, i+3):
  13.             if j < n:
  14.                 if i == j and s[j] == '0':
  15.                     backtrack(j+1, tmp + s[j] + '.', flag-1)
  16.                     break
  17.                 if 0 < int(s[i:j+1]) <= 255:
  18.                     backtrack(j+1, tmp + s[i:j+1] + '.', flag-1)
  20.     backtrack(0, '',4)
  21.     return res