算法题--将字符串划分为若干个回文

image.png

0. 链接

题目链接

1. 题目

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]

2. 思路1: 回溯+动态规划

1. 基本思路是:

• 从左到右依次尝试以每个字母作为回文的中心点, 向左向右尽量扩展, 如果从start到i构成回文, 则记录dp[i][start]=True, 然后继续更新start为i+1, 继续向右查找其他回文中心点
• 例如对于abcba
  • 先尝试从第0位的a作为回文中心点, 则start=i=0, 记录dp[0][0] = True
  • start先一直右移(深度优先搜索), 不断得到
    dp[1][1] = dp[2][2] = dp[3][3] = dp[4][4] = True
    , 得到第一组合法的回文列表['a', 'b', 'c', 'b', 'a'], 即每个字母单独成为回文.
  • 接下来回溯倒数第二步, 即start=3时, i=3已经遍历过, 再尝试i = 4, 则经过判断s[3] != s[4], 构不成回文, 于是此次回溯失败, start=3的可能情况已经尝试完毕
  • 接下来继续回溯start=2的情况, i = 2已经遍历过, 接下来开始遍历i=3,4, 对于i=3, 由于s[2] != s[3], 则回溯失败; 对于i=4, s[2] != s[3], 也回溯失败, 于是start=2的可能情况也已经尝试完毕
  • 接下来继续回溯start=1的情况, i=1已经尝试过, 继续尝试i=2,3,4, s[start=1] != s[i = 2], 但s[start=1]==s[i = 3], 找到一个成功的结果, 则记录 dp[1][3] = True, 并得到分割结果['a', 'bcb', 'a']
  • 同理start=0的情况, 满足s[start=0] == s[i=4] 且 dp[start + 1][i - 1] = dp[1][3] = True, 则直接记录dp[0][4] = True, 并得到分割结果['abcba']
  • 收集所有结果，得到返回值[['a', 'b', 'c', 'b', 'a'], ['a', 'bcb', 'a'], ['abcba']]

2. 分析:

• 过程中, 尝试以每个节点作为start的时候, 由于回溯的存在, 对于每个start~n-1的元素, 都需要尝试一遍, 因此时间复杂度是O(n^2), 动态规划所用的dp耗费存储空间为O(n^2)

3. 复杂度

• 时间复杂度 O(n^2)
• 空间复杂度 O(n^2)

3. 代码

# coding:utf8
from typing import List


class Solution:
    def partition(self, s: str) -> List[List[str]]:
        rtn_list = list()
        path = list()
        length = len(s)
        dp = [[False] * length for _ in range(length)]
        self.dfs(rtn_list, path, s, 0, length, dp)
        return rtn_list

    def dfs(self, rtn_list, path, s, start, length, dp):
        if start == length:
            rtn_list.append(path.copy())
        else:
            for i in range(start, length):
                if s[start] != s[i]:
                    continue
                if i - 1 > start + 1 and not dp[i - 1][start + 1]:
                    continue
                dp[i][start] = True
                path.append(s[start: i + 1])
                self.dfs(rtn_list, path, s, i + 1, length, dp)
                path.pop()


def my_test(solution, s):
    print('input: s={}; output: {}'.format(s, solution.partition(s)))


solution = Solution()
my_test(solution, 'aab')
my_test(solution, 'bb')

输出结果

input: s=aab; output: [['a', 'a', 'b'], ['aa', 'b']]
input: s=bb; output: [['b', 'b'], ['bb']]

4. 结果

image.png