算法学习

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

2020-05-07  本文已影响0人  岁月如歌2020
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. 基本思路是:
  1. 分析:
  1. 复杂度

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
上一篇 下一篇

猜你喜欢

热点阅读