leetcode—Palindrome 解題報告

1.題目描述

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"]
  ]

也就是給定一個字符串，找出所有可能的劃分，每一個劃分的每一個字串都是回文串。設這個劃分函數為partition_index(string s,int begin,int end)

2.解題思路

蠻力法當然是可以解決這個問題，對於一個長度為n的字符串，有2^n-1種劃分方法，只需要判斷每種劃分是否滿足條件即可，雖然不知道暴力法能不能在系統裡面ac掉，但是這樣顯然不是一個正常的程序員該干的事。不過蠻力法會給我們一些啟示。我們從為什麼蠻力法會有2^n-1種劃分方法開始分析。

當然，這也很容易分析，對於長度為n的字符串s₀s₁…s_k…s_n-1,在s_k和s_k-1之間我們可以選擇截斷與不截斷，但是，我們可以基於這個思路理出一個遞歸的思路，那就是，對於字符串s_begins_begin+1…s_begin+k…s_n-1,所有可能滿足條件的劃分分為兩類：

（1）在s_begin和s_begin+1之間有隔斷，這種情況，只需s_begin和partition_index(s,begin+1,n-1)連接起來即可

（2）在s_begin和s_begin+1之間無隔斷，這種情況，需找到至少包含s_begin和s_begin+1的一個回文字符串，如果能夠找到，比如，s_begin…s_begin+k是一個回文字符串，那麼，將這個回文字符串和partition_index(s,k+1,n-1)連接起來，注意，可能找到不止一個包含s₀和s₁的回文字符串，那麼有多少個，就多出多少類劃分可能；如果找不到，那麼返回空vector.

3.代碼

另外,代碼可以簡化,比如,連接結果的代碼可以封裝成一個函數.