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;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }