Daily classic

Climbing the Stork Building — Wang Zhihuan (Tang Dynasty)

Day according to the mountains, the Yellow River into the sea.

To see a thousand miles, to the next level.

describe

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Copy the code

Example 2:

Input: s = "a"
Output: [["a"]]
Copy the code

Note:

1 <= s.length <= 16
s contains only lowercase English letters.
Copy the code

parsing

Given a string s, partition s such that each substring of the partition is a palindrome. Returns all possible palindrome partitions of S. The palindrome string is the same string read backwards as read forwards.

This problem is a typical DFS + dynamic programming problem, very classic. If s[I][j] is a palindrome string, use the dynamic programming array dp[I][j]. Then use DFS to find all the combinations.

answer

import numpy as np
class Solution(object):
    def __init__(self):
        self.dp = None
        self.result = []
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        N = len(s)
        self.dp = [[False]*N for _ in range(N)]
        for i in range(N):
            self.dp[i][i] = True
        for i in range(N-1):
            self.dp[i][i+1] = (s[i] == s[i+1])
        for L in range(3, N+1):
            for i in range(N-L+1):
                j = i+L-1
                if s[i]==s[j] and self.dp[i+1][j-1]:
                    self.dp[i][j] = True
        self.dfs(0, [], s, N)
        return self.result
    
    def dfs(self, i, t, s, N):
        if i == N:
            self.result.append(t)
            return 
        for j in range(i, N):
            if self.dp[i][j]:
                self.dfs(j+1, t+[s[i:j+1]], s, N)
        
      	      
		
Copy the code

The results

Given the submission in the Python online submissions to the node. Given in the Python online submissions for Palindrome Partitioning.Copy the code

Original link: leetcode.com/problems/pa…

Your support is my biggest motivation