本文共 2204 字，大约阅读时间需要 7 分钟。

https://oj.leetcode.com/problems/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"]  ]

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

在正式介绍解法之前，首先想先阐述一个跟palindrome有关的二维DP算法。

f(i,j) = true if i == j

f(i,j) = S[i] == S[j] if i == j - 1

f(i,j) = f(i + 1, j - 1) && S[i] == S[j] if i < j - 1

f(i,j)表示的就是s[i..j]是否为palindrome。

这样就可以用O(N^2）得到这个数组里所有的palindrome，用一个二维数组表示。

代码如下：

boolean[][] dp = new boolean[s.length()][s.length()];        for(int i = 0; i < s.length(); i++)            dp[i][i] = true;        for(int dist = 1; dist < s.length(); dist++){            for(int i = 0; i < s.length() - dist; i++){                dp[i][i + dist] = s.charAt(i) == s.charAt(i + dist) && (dist == 1 ? true : dp[i + 1][i + dist - 1]);            }        }

这一题其实就是DFS的暴力递归，除此之外我暂时还想不到别的做法，因为很明显解集的数量上限是指数级的，所以用指数级的算法也应该是可以的。

简单来说就是在每一层保持一个头，然后从头开始循环看头尾之间是否palindrome,是的话就往下递归一层的同时这一层继续循环。其实就是backtrace。代码如下

//high efficiency solution with dp    public List
   
    
     > partition(String s) {        List
     
      
       > res = new LinkedList
       
        
         >(); boolean[][] dp = new boolean[s.length()][s.length()]; for(int i = 0; i < s.length(); i++) dp[i][i] = true; for(int dist = 1; dist < s.length(); dist++){ for(int i = 0; i < s.length() - dist; i++){ dp[i][i + dist] = s.charAt(i) == s.charAt(i + dist) && (dist == 1 ? true : dp[i + 1][i + dist - 1]); } } Helper(s, 0, new LinkedList
         
          (), res, dp); return res; } public void Helper(String s, int start, List
          
            cur_res, List
           
            
             > res, boolean[][] dp){ if(start == s.length()){ res.add(cur_res); return; } for(int i = start; i < s.length(); i++){ if(dp[start][i]){ List
             
               next_res = new LinkedList
              
               (cur_res); next_res.add(s.substring(start, i + 1)); Helper(s, i + 1, next_res, res, dp); } } } public boolean isValid(int start, int end, String s){ while(start < end){ if(s.charAt(start) != s.charAt(end)){ return false; } start++; end--; } return true; }
              
             
            
           
          
         
        
       
      
     
    
   

你可以看到我这里放了一个函数isValid，其实在Helper函数中，把dp[start][i]换成isValid(start, i, s)也是可以过的。只是如果套用我刚才的dp算法，效率上会少一个N的倍数。

转载地址：http://qgaxb.baihongyu.com/