首页 > 搜索 > BFS搜索 > LeetCode-Palindrome Partitioning[回溯]
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"]
  ]

题目链接:https://oj.leetcode.com/problems/palindrome-partitioning/

 分析

此题可以用回溯法(DFS搜索)解决。把字符串s分为前后两个字串 str1, str2;如果str1是回文,加入partition,然后递归str2.

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>();
	addPalindrome(s, 0, partition, result);

	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中
		result.add(temp);
		return;
	}

	for (int i = start + 1; i <= s.length(); i++) {
		String str = s.substring(start, i);
		if (isPalindrome(str)) {
			partition.add(str);
			addPalindrome(s, i, partition, result);
			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. 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.

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