Java for LeetCode 131 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"]
]
解题思路一：

将s分为左右两个部分，分别求出两边的partition，然后粘一块即可，JAVA实现如下：

	static public List<List<String>> partition(String s) {

		Set<List<String>> set = new HashSet<List<String>>();

		if (isPalindrome(s)) {

			List<String> alist = new ArrayList<String>();

			alist.add(s);

			set.add(alist);

		}

		for (int i = 1; i < s.length(); i++) {

			List<List<String>> left = partition(s.substring(0, i));

			List<List<String>> right = partition(s.substring(i, s.length()));

			for (List<String> aLeft : left)

				for (List<String> aRight : right) {

					List<String> alist = new ArrayList<String>(aLeft);

					alist.addAll(aRight);

					set.add(new ArrayList<String>(alist));

				}

		}

		return new ArrayList<List<String>>(set);

	}

	static boolean isPalindrome(String s) {

		int left = 0;

		int right = s.length() - 1;

		while (left < right)

			if (s.charAt(left++) != s.charAt(right--))

				return false;

		return true;

	}

结果TLE

解题思路二：

修改下思路一，从左边入手，如果左边是Palindrome，对右边求一个partition，这样求得的结果也不会重复，这样就可以AC了，JAVA实现如下：

	static public List<List<String>> partition(String s) {

		ArrayList<List<String>> list = new ArrayList<List<String>>();

		if (isPalindrome(s)) {

			List<String> alist = new ArrayList<String>();

			alist.add(s);

			list.add(alist);

		}

		for (int i = 1; i < s.length(); i++)

			if (isPalindrome(s.substring(0, i))) {

				List<String> aLeft = new ArrayList<String>();

				aLeft.add(s.substring(0, i));

				List<List<String>> right = partition(s.substring(i, s.length()));

				for (List<String> aRight : right) {

					List<String> alist = new ArrayList<String>(aLeft);

					alist.addAll(aRight);

					list.add(new ArrayList<String>(alist));

				}

			}

		return list;

	}

	static boolean isPalindrome(String s) {

		int left = 0;

		int right = s.length() - 1;

		while (left < right)

			if (s.charAt(left++) != s.charAt(right--))

				return false;

		return true;

	}

巴特西

Java for LeetCode 131 Palindrome Partitioning

最新文章

热门文章