回文

偏执的太偏执、 2022-02-25 10:24 205阅读 0赞

【题目】  
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”\]  
\]  
**（译）**  
给定一个字符串s，划分s使得划分的每个子字符串都是一个回文，返回s的所有可能情况  
例如：s = “aab”  
返回 ：\[ \[“aa”,“b”\], \[“a”,“a”,“b”\] \]

【思路】  
回溯法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
【实现】

import java.util.ArrayList;
    import java.util.List;
     
    public class Solution {
      public static ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> lists = new ArrayList<>();
        ArrayList<String> list = new ArrayList<>();
        partitionHepler(lists, list, s);
        System.out.println(lists);
        return lists;
      }
     
      public static void partitionHepler(ArrayList<ArrayList<String>> lists, ArrayList<String> list, String s) {
        if (null == s || s.length() == 0) {
          lists.add(new ArrayList<>(list));
          return;
        }
        int len = s.length();
        for (int i = 0; i <= len;i++) {
          String subStr = s.substring(0, i);
          if (isPalindrome(subStr)) {
            list.add(subStr);
            partitionHepler(lists, list, s.substring(i, len));
            list.remove(list.size() - 1);
          }
        }
      }
     
      public static boolean isPalindrome(String s) {
        if (null == s || s.length() == 0) return false;
        int length = s.length();
        int middle = length / 2;
        for (int i = 0; i < middle;i++) {
          if (s.charAt(i) != s.charAt(length - 1 - i)) {
            return false;
          }
        }
        return true;
      }
    
        public static void main(String[] args) {
    		String s = "aab";
    		partition(s);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220225/09734e54231347bea3db5c656a0f8814.png