Skip to content

1278. Palindrome Partitioning III 👍

Approach 1: Top-down

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int palindromePartition(string s, int k) {
    const int n = s.length();
    vector<vector<int>> mem(n + 1, vector<int>(k + 1, n));
    // cost[i][j] := the minimum cost to make s[i..j] palindrome
    vector<vector<int>> cost(n, vector<int>(n));

    for (int d = 1; d < n; ++d)
      for (int i = 0, j = d; j < n; ++i, ++j)
        cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1];

    return palindromePartition(n, k, cost, mem);
  }

 private:
  // Returns the minimum cost to make k palindromes by s[0..i).
  int palindromePartition(int n, int k, const vector<vector<int>>& cost,
                          vector<vector<int>>& mem) {
    if (k == 1)
      return cost[0][n - 1];
    if (mem[n][k] < n)
      return mem[n][k];

    // Try all the possible partitions.
    for (int i = k - 1; i < n; ++i)
      mem[n][k] = min(
          mem[n][k], palindromePartition(i, k - 1, cost, mem) + cost[i][n - 1]);

    return mem[n][k];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int palindromePartition(String s, int k) {
    final int n = s.length();
    int[][] mem = new int[n + 1][k + 1];
    // cost[i][j] := the minimum cost to make s[i..j] palindrome
    int[][] cost = new int[n][n];

    Arrays.stream(mem).forEach(A -> Arrays.fill(A, n));

    for (int d = 1; d < n; ++d)
      for (int i = 0, j = d; j < n; ++i, ++j)
        cost[i][j] = (s.charAt(i) == s.charAt(j) ? 0 : 1) + cost[i + 1][j - 1];

    return palindromePartition(n, k, cost, mem);
  }

  // Returns the minimum cost to make k palindromes by s[0..i).
  private int palindromePartition(int n, int k, int[][] cost, int[][] mem) {
    if (k == 1)
      return cost[0][n - 1];
    if (mem[n][k] < n)
      return mem[n][k];

    // Try all the possible partitions.
    for (int i = k - 1; i < n; ++i)
      mem[n][k] = Math.min(mem[n][k], //
                           palindromePartition(i, k - 1, cost, mem) + cost[i][n - 1]);

    return mem[n][k];
  }
}

Approach 2: Bottom-up

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int palindromePartition(string s, int K) {
    const int n = s.length();
    // dp[i][k] := the minimum cost to make k palindromes by s[0..i)
    vector<vector<int>> dp(n + 1, vector<int>(K + 1, n));
    // cost[i][j] := the minimum cost to make s[i..j] palindrome
    vector<vector<int>> cost(n, vector<int>(n));

    for (int d = 1; d < n; ++d)
      for (int i = 0, j = d; j < n; ++i, ++j)
        cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1];

    for (int i = 1; i <= n; ++i)
      dp[i][1] = cost[0][i - 1];

    for (int k = 2; k <= K; ++k)
      for (int i = k; i <= n; ++i)
        for (int j = k - 1; j < i; ++j)
          dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost[j][i - 1]);

    return dp[n][K];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int palindromePartition(String s, int K) {
    final int n = s.length();
    // dp[i][k] := the minimum cost to make k palindromes by s[0..i)
    int[][] dp = new int[n + 1][K + 1];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, n));
    // cost[i][j] := the minimum cost to make s[i..j] palindrome
    int[][] cost = new int[n][n];

    for (int d = 1; d < n; ++d)
      for (int i = 0, j = d; j < n; ++i, ++j)
        cost[i][j] = (s.charAt(i) == s.charAt(j) ? 0 : 1) + cost[i + 1][j - 1];

    for (int i = 1; i <= n; ++i)
      dp[i][1] = cost[0][i - 1];

    for (int k = 2; k <= K; ++k)
      for (int i = k; i <= n; ++i)
        for (int j = k - 1; j < i; ++j)
          dp[i][k] = Math.min(dp[i][k], dp[j][k - 1] + cost[j][i - 1]);

    return dp[n][K];
  }
}