首页 > 代码库 > Leetcode 131. Palindrome Partitioning
Leetcode 131. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab"
,
Return
[ ["aa","b"], ["a","a","b"] ]
Keys: 1. 一般列出所有组合,可能性,etc 的题目都可以用DFS.
2. L8. 对于Class Solution中的全局变量x,可以用Solution.x
1 class Solution(object): 2 def partition(self, s): 3 """ 4 :type s: str 5 :rtype: List[List[str]] 6 """ 7 Solution.res = [] 8 self.DFS(s, []) 9 return Solution.res 10 11 def DFS(self, s, stringlist): 12 if len(s) == 0: 13 Solution.res.append(stringlist) 14 # 如果一开始的substring是palin,把他存到stringlist中 15 for i in range(1, len(s)+1): 16 if self.isPalin(s[:i]): 17 self.DFS(s[i:], stringlist + [s[:i]]) 18 19 20 def isPalin(self, s): 21 for i in range(len(s)): 22 if s[i] != s[len(s)-1-i]: 23 return False 24 return True 25 26
Leetcode 131. Palindrome Partitioning
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。