leetcode 131. Palindrome Partitioning | 131. 分割回文串（递归解法）

客官°小女子只卖身不卖艺 2022-08-30 15:51 140阅读 0赞

## 题目 ##

[https://leetcode.com/problems/palindrome-partitioning/][https_leetcode.com_problems_palindrome-partitioning]  
![在这里插入图片描述][d21865cee8fd3899c3029e70cad2bdd4.png]

## 题解 ##

中规中矩的递归，因为每一层都需要在上一层保存好的 list 的基础上继续，而且不能影响下一层递归，所以做了一些 local 化的操作，自我感觉不是很优雅。

更好的解法可以参考：[官方题解][Link 1]

class Solution { 
        public List<List<String>> partition(String s) { 
            List<List<String>> result = new ArrayList<>();
            List<String> curList = new ArrayList<>();
            process(s, 0, curList, result);
            return result;
        }
    
        public void process(String s, int begin, List<String> curList, List<List<String>> result) { 
            if (begin >= s.length()) return;
            if (isPalindrome(s, begin, s.length() - 1)) { 
                List<String> temp = new ArrayList<>(curList);
                temp.add(s.substring(begin, s.length()));
                result.add(temp);
            }
            List<String> local;
            for (int i = begin; i < s.length(); i++) { 
                if (isPalindrome(s, begin, i)) { 
                    local = new ArrayList<>(curList);
                    local.add(s.substring(begin, i + 1));
                    process(s, i + 1, local, result);
                }
            }
        }
    
        public boolean isPalindrome(String s, int i, int j) { 
            while (i < j) { 
                if (s.charAt(i) != s.charAt(j)) return false;
                i++;
                j--;
            }
            return true;
        }
    }

![在这里插入图片描述][0da24f61e05a44b7e6e40ddc186bae26.png]

[https_leetcode.com_problems_palindrome-partitioning]: https://leetcode.com/problems/palindrome-partitioning/
[d21865cee8fd3899c3029e70cad2bdd4.png]: /images/20220829/21bb37c72fd74abfacd53a74142ecc7b.png
[Link 1]: https://leetcode.com/problems/palindrome-partitioning/solution/
[0da24f61e05a44b7e6e40ddc186bae26.png]: /images/20220829/7fc15c76557943edb3b4e0b7acbced9e.png