131. Palindrome Partitioning

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

思路： 本题考查回溯算法。从下标0开始遍历字符串，一旦在下标 i 找到回文子字符串，那么就把下标从 0 到 i 的子字符串加入temp中，继续从下标 i 接着往下找，一旦curIndex等于字符串长度，那么就把temp加入到result中。如果一直到最后都没找到回文子字符串，那么就进行剪枝。

class Solution { public List> partition(String s) { List> result = new ArrayList>(); List temp = new ArrayList(); dfs(s, 0, temp, result); return result; } private void dfs(String s, int curIndex, List temp, List> result) { if (curIndex == s.length()) { result.add(new ArrayList(temp)); return; } for (int i = curIndex + 1; i <= s.length(); i++) { String prefix = s.substring(curIndex, i); if (!isPrlindrome(prefix)) //剪枝 continue; temp.add(prefix); dfs(s, i, temp, result); temp.remove(temp.size() - 1); } } private boolean isPrlindrome(String s) { int left = 0; int right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) return false; left++; right--; } return true; } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。