description: 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 class Solution { public List<List<String>> partition(String s) { List<List<String>> result = new ArrayList<>(); if (s == null || s.length() == 0) { return result; } List<String> arr = new ArrayList<>(); util(result, arr, s,0); return result; } PRivate void util(List<List<String>> result, List<String> arr, String s, int start){ if (start == s.length()) { result.add(new ArrayList<>(arr)); return; } for (int i = start; i < s.length(); i++) { String substr = s.substring(start, i + 1); if (isPalindrome(substr)) { arr.add(substr); util(result, arr, s, i + 1); arr.remove(arr.size() - 1); } } } private boolean isPalindrome(String str) { if (str.length() == 0) { return true; } int left = 0; int right = str.length() - 1; while (left <= right) { if(str.charAt(left++) != str.charAt(right--)) { return false; } } return true; }}新闻热点
疑难解答
