Question

132. Palindrome Partitioning II

中文文档

Description

Given a string s, partition s such that every substring of the partition is a palindrome.

Return _the minimum cuts needed for a palindrome partitioning of_ s.

 

Example 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

Input: s = "a"
Output: 0

Example 3:

Input: s = "ab"
Output: 1

 

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase English letters only.

Solutions

Solution 1

class Solution:
  def minCut(self, s: str) -> int:
    n = len(s)
    g = [[True] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
      for j in range(i + 1, n):
        g[i][j] = s[i] == s[j] and g[i + 1][j - 1]
    f = list(range(n))
    for i in range(1, n):
      for j in range(i + 1):
        if g[j][i]:
          f[i] = min(f[i], 1 + f[j - 1] if j else 0)
    return f[-1]

class Solution {
  public int minCut(String s) {
    int n = s.length();
    boolean[][] g = new boolean[n][n];
    for (var row : g) {
      Arrays.fill(row, true);
    }
    for (int i = n - 1; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        g[i][j] = s.charAt(i) == s.charAt(j) && g[i + 1][j - 1];
      }
    }
    int[] f = new int[n];
    for (int i = 0; i < n; ++i) {
      f[i] = i;
    }
    for (int i = 1; i < n; ++i) {
      for (int j = 0; j <= i; ++j) {
        if (g[j][i]) {
          f[i] = Math.min(f[i], j > 0 ? 1 + f[j - 1] : 0);
        }
      }
    }
    return f[n - 1];
  }
}

class Solution {
public:
  int minCut(string s) {
    int n = s.size();
    bool g[n][n];
    memset(g, true, sizeof(g));
    for (int i = n - 1; ~i; --i) {
      for (int j = i + 1; j < n; ++j) {
        g[i][j] = s[i] == s[j] && g[i + 1][j - 1];
      }
    }
    int f[n];
    iota(f, f + n, 0);
    for (int i = 1; i < n; ++i) {
      for (int j = 0; j <= i; ++j) {
        if (g[j][i]) {
          f[i] = min(f[i], j ? 1 + f[j - 1] : 0);
        }
      }
    }
    return f[n - 1];
  }
};

func minCut(s string) int {
  n := len(s)
  g := make([][]bool, n)
  f := make([]int, n)
  for i := range g {
    g[i] = make([]bool, n)
    f[i] = i
    for j := range g[i] {
      g[i][j] = true
    }
  }
  for i := n - 1; i >= 0; i-- {
    for j := i + 1; j < n; j++ {
      g[i][j] = s[i] == s[j] && g[i+1][j-1]
    }
  }
  for i := 1; i < n; i++ {
    for j := 0; j <= i; j++ {
      if g[j][i] {
        if j == 0 {
          f[i] = 0
        } else {
          f[i] = min(f[i], f[j-1]+1)
        }
      }
    }
  }
  return f[n-1]
}

function minCut(s: string): number {
  const n = s.length;
  const g: boolean[][] = Array(n)
    .fill(0)
    .map(() => Array(n).fill(true));
  for (let i = n - 1; ~i; --i) {
    for (let j = i + 1; j < n; ++j) {
      g[i][j] = s[i] === s[j] && g[i + 1][j - 1];
    }
  }
  const f: number[] = Array(n)
    .fill(0)
    .map((_, i) => i);
  for (let i = 1; i < n; ++i) {
    for (let j = 0; j <= i; ++j) {
      if (g[j][i]) {
        f[i] = Math.min(f[i], j ? 1 + f[j - 1] : 0);
      }
    }
  }
  return f[n - 1];
}

public class Solution {
  public int MinCut(string s) {
    int n = s.Length;
    bool[,] g = new bool[n,n];
    int[] f = new int[n];
    for (int i = 0; i < n; ++i) {
      f[i] = i;
      for (int j = 0; j < n; ++j) {
        g[i,j] = true;
      }
    }
    for (int i = n - 1; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        g[i,j] = s[i] == s[j] && g[i + 1,j - 1];
      }
    }
    for (int i = 1; i < n; ++i) {
      for (int j = 0; j <= i; ++j) {
        if (g[j,i]) {
          f[i] = Math.Min(f[i], j > 0 ? 1 + f[j - 1] : 0);
        }
      }
    }
    return f[n - 1];
  }
}