2014
10-02

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

分析

public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();

if (s == null || s.length() == 0) {
return result;
}

ArrayList<String> partition = new ArrayList<String>();

return result;
}

//start为开始的位置, partition存放当前的分割结果
private void addPalindrome(String s, int start, ArrayList<String> partition,
ArrayList<ArrayList<String>> result) {
//返回条件
if (start == s.length()) {
ArrayList<String> temp = new ArrayList<String>(partition);//partition复制到temp中
return;
}

for (int i = start + 1; i <= s.length(); i++) {
String str = s.substring(start, i);
if (isPalindrome(str)) {
partition.remove(partition.size() - 1);//回溯
}
}
}

private boolean isPalindrome(String str) {
int left = 0;
int right = str.length() - 1;

while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}

left++;
right--;
}

return true;
}

1. 为何你针对这个麦田圈案例 确刻意回避我提出的问题 不去看其他明显非人为的麦田圈案例 这一点让一个沉迷在网上找轮子麻烦的人感到一阵亲切感呀 同样的执着撞南墙也不回头精神就这个案例来说 请问你给出一个介绍别人软件的网页就直接信口开河这个麦田圈只是一个平面广告

2. Gucci New Fall Arrivals

This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

3. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。