程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode Palindrome Partitioning

LeetCode Palindrome Partitioning

編輯:關於C++

LeetCode解題之Palindrome Partitioning


原題

將一個字符串分割成若干個子字符串,使得子字符串都是回文字符串,要求列出所有的分割方案。

注意點:

例子:

輸入: s = “aab”

輸出: result = [[“a”, “a”, “b”], [“aa”, “b”]]

解題思路

采用了最簡單的遞歸方法,將一個字符串分為前後兩部分,如果第一部分是一個回文字符串,則對第二部分再次分割,不斷遞歸,直到遞歸的終止條件——字符串為空為止;如果第一部分不是一個回文字符串,則嘗試下一種分割方法。

AC源碼

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        if not s:
            return [[]]
        result = []
        for i in range(len(s)):
            if self.isPalindrome(s[:i + 1]):
                for r in self.partition(s[i + 1:]):
                    result.append([s[:i + 1]] + r)
        return result

    def isPalindrome(self, s):
        return s == s[::-1]


if __name__ == "__main__":
    assert Solution().partition("aab") == [
        ["a", "a", "b"],
        ["aa", "b"]
    ]
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved