leetCode解題報告

題目：

Palindrome Partitioning  I

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

  ]

分析：

題意給我們一個字元串，求出所有這個字元串的子串，并且子串都為回文字元串的情況，輸出它的集合結果

解題思路：（跟DFS深度周遊有點像!）

字元串Str = "aab";

分析了題目的資料之後，我們知道它的結果，可能是 a, a, b 或者  aa, b 這樣的情況！

也就是說，我們需要去考慮 i = 1,  2 ....  n 的情況，比如

Str = "aaa"

結果集

[[a, a, a], [a, aa], [aa, a], [aaa]]

根據這樣的情況，我們用類似于DFS的算法

str1 = str.substr(0, i); 取出前面下标從 0 開始到 i 結束的子串，判斷str1是否滿足回文字元串的要求，

1. 滿足：這樣子，有可能成為一種分割的情況，是以我們new出一個list集合，把str1放入到list中，然後我們求出str剩餘的子串  str2 = str.substr(i); 取出前面下标從 i 開始到整個字元串結尾的子串， 然後将str2 作為新的字元串，同時把list集合也傳入到函數中，遞歸調用。遞歸的結束條件就是到傳入的這個字元串的長度為0（這樣就意味着已經到了字元串的末尾了），此時證明這種情況下得到的list集合是滿足條件的，我們把這個list集合 加入到 結果集合result中。

2. 不滿足的話，繼續 i++， 直到 i == str.length();

3. 全部結束之後，傳回 最終的結果集合 result