leetcode131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

思路：搜索回溯，搜索过程中检查是否是回文。

  

   

    

     

    
    

     

      public class Solution {
     
    
   

    

     

    
    

     

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

    

     

    
    

     
 // Stack 这个类 Java 的文档里推荐写成 Deque<Integer> stack = new ArrayDeque<Integer>();
     
    
   

    

     

    
    

     
 // 注意：只使用 stack 相关的接口
     
    
   

    

     

    
    

     

       Deque<String> stack = new ArrayDeque<>();
     
    
   

    

     

    
    

     
 int len;
     
    
   

    

     

    
    

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

    

     

    
    

     

       len = s.length();
     
    
   

    

     

    
    

     
 if (len == 0) return res;
     
    
   

    

     

    
    

     

       backtracking(s, 0);
     
    
   

    

     

    
    

     
 return res;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 private void backtracking(String s, int start) {
     
    
   

    

     

    
    

     
 if (start == len) {
     
    
   

    

     

    
    

     

       res.add(new ArrayList<>(stack));
     
    
   

    

     

    
    

     
 return;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for (int i = start; i < len; i++) {
     
    
   

    

     

    
    

     
 if (checkPalindrome(s, start, i)) {
     
    
   

    

     

    
    

     

       stack.addLast(s.substring(start, i + 1));
     
    
   

    

     

    
    

     

       backtracking(s, i + 1);
     
    
   

    

     

    
    

     

       stack.removeLast();
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 private boolean checkPalindrome(String str, int left, int right) {
     
    
   

    

     

    
    

     
 while (left < right) {
     
    
   

    

     

    
    

     
 if (str.charAt(left) != str.charAt(right)) return false;
     
    
   

    

     

    
    

     

       left++;right--;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return true;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104410030