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

  1.   [
  2.     ["aa","b"],
  3.     ["a","a","b"]
  4.   ]

分析

在每一步都可以判断中间结果是否为合法结果，用回溯法。

一个长度为n的字符串，有n-1个地方可以砍断，每个地方可断可不断，因此复杂度为O(2n−1)O(2^{n-1})

深搜1

  1. // Palindrome Partitioning
  2. // 时间复杂度O(2^n)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<List<String>> partition(String s) {
  5.         List<List<String>> result = new ArrayList<>();
  6.         List<String> path = new ArrayList<>(); // 一个partition方案
  7.         dfs(s, path, result, 0, 1);
  8.         return result;
  9.     }
  11.     // prev 表示前一个隔板, start 表示当前隔板
  12.     private static void dfs(String s, List<String> path,
  13.                             List<List<String>> result, int prev, int start) {
  14.         if (start == s.length()) { // 最后一个隔板
  15.             if (isPalindrome(s, prev, start - 1)) { // 必须使用
  16.                 path.add(s.substring(prev, start));
  17.                 result.add(new ArrayList<>(path));
  18.                 path.remove(path.size() - 1);
  19.             }
  20.             return;
  21.         }
  22.         // 不断开
  23.         dfs(s, path, result, prev, start + 1);
  24.         // 如果[prev, start-1] 是回文，则可以断开，也可以不断开（上一行已经做了）
  25.         if (isPalindrome(s, prev, start - 1)) {
  26.             // 断开
  27.             path.add(s.substring(prev, start));
  28.             dfs(s, path, result, start, start + 1);
  29.             path.remove(path.size() - 1);
  30.         }
  31.     }
  33.     private static boolean isPalindrome(String s, int start, int end) {
  34.         while (start < end && s.charAt(start) == s.charAt(end)) {
  35.             ++start;
  36.             --end;
  37.         }
  38.         return start >= end;
  39.     }
  40. }

深搜2

另一种写法，更加简洁。这种写法也在 Combination Sum, Combination Sum II 中出现过。

  1. // Palindrome Partitioning
  2. // 时间复杂度O(2^n)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<List<String>> partition(String s) {
  5.         List<List<String>> result = new ArrayList<>();
  6.         List<String> path = new ArrayList<>();  // 一个partition方案
  7.         dfs(s, path, result, 0);
  8.         return result;
  9.     }
  10.     // 搜索必须以s[start]开头的partition方案
  11.     private static void dfs(String s, List<String> path,
  12.                             List<List<String>> result, int start) {
  13.         if (start == s.length()) {
  14.             result.add(new ArrayList<>(path));
  15.             return;
  16.         }
  17.         for (int i = start; i < s.length(); i++) {
  18.             if (isPalindrome(s, start, i)) { // 从i位置砍一刀
  19.                 path.add(s.substring(start, i+1));
  20.                 dfs(s, path, result, i + 1);  // 继续往下砍
  21.                 path.remove(path.size() - 1); // 撤销上上行
  22.             }
  23.         }
  24.     }
  25.     private static boolean isPalindrome(String s, int start, int end) {
  26.         while (start < end && s.charAt(start) == s.charAt(end)) {
  27.             ++start;
  28.             --end;
  29.         }
  30.         return start >= end;
  31.     }
  32. }

动规

  1. // Palindrome Partitioning
  2. // 动规，时间复杂度O(n^2)，空间复杂度O(1)
  3. public class Solution {
  4.     public List<List<String>> partition(String s) {
  5.         final int n = s.length();
  6.         boolean[][] p = new boolean[n][n]; // whether s[i,j] is palindrome
  7.         for (int i = n - 1; i >= 0; --i)
  8.             for (int j = i; j < n; ++j)
  9.                 p[i][j] = s.charAt(i) == s.charAt(j) &&
  10.                         ((j - i < 2) || p[i + 1][j - 1]);
  12.         List<List<String>>[] subPalins = new ArrayList[n]; // sub palindromes of s[0,i]
  13.         for (int i = 0; i < n; ++i) subPalins[i] = new ArrayList<>();
  14.         for (int i = n - 1; i >= 0; --i) {
  15.             for (int j = i; j < n; ++j)
  16.                 if (p[i][j]) {
  17.                     String palindrome = s.substring(i, j+1);
  18.                     if (j + 1 < n) {
  19.                         for (List<String> v : subPalins[j + 1]) {
  20.                             ArrayList<String> tmp = new ArrayList<>(v);
  21.                             tmp.add(0, palindrome);
  22.                             subPalins[i].add(tmp);
  23.                         }
  24.                     } else {
  25.                         ArrayList<String> tmp = new ArrayList<>();
  26.                         tmp.add(palindrome);
  27.                         subPalins[i].add(tmp);
  28.                     }
  29.                 }
  30.         }
  31.         return subPalins[0];
  32.     }
  33. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dfs/palindrome-partitioning.html