Skip to content

1745. Palindrome Partitioning IV 👍

Approach 1: Top-down

  • Time: $O(n^2)$
  • 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
class Solution {
 public:
  bool checkPartitioning(string s) {
    const int n = s.length();
    // dp[i][j] := true if s[i..j] is palindrome
    dp.resize(n, vector<int>(n, -1));

    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j)
        if (isPalindrome(s, 0, i) && isPalindrome(s, i + 1, j) &&
            isPalindrome(s, j + 1, n - 1))
          return true;

    return false;
  }

 private:
  vector<vector<int>> dp;

  // Returns 0 if s[i..j] is not a palindrome
  // Returns 1 if s[i..j] is a palindrome
  int isPalindrome(const string& s, int i, int j) {
    if (i > j)
      return 1;
    if (dp[i][j] != -1)
      return dp[i][j];
    if (s[i] == s[j])
      return dp[i][j] = isPalindrome(s, i + 1, j - 1);
    return dp[i][j] = 0;
  }
};

 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
class Solution {
  public boolean checkPartitioning(String s) {
    final int n = s.length();
    // dp[i][j] := true if s[i..j] is palindrome
    dp = new int[n][n];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, -1));

    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j)
        if (isPalindrome(s, 0, i) == 1 && isPalindrome(s, i + 1, j) == 1 &&
            isPalindrome(s, j + 1, n - 1) == 1)
          return true;

    return false;
  }

  private int[][] dp;

  // Returns 0 if s[i..j] is not a palindrome
  // Returns 1 if s[i..j] is a palindrome
  int isPalindrome(final String s, int i, int j) {
    if (i > j)
      return 1;
    if (dp[i][j] != -1)
      return dp[i][j];
    if (s.charAt(i) == s.charAt(j))
      return dp[i][j] = isPalindrome(s, i + 1, j - 1);
    return dp[i][j] = 0;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def checkPartitioning(self, s: str) -> bool:
    # dp(i, j) := True if s[i:j] is a palindrome
    @functools.lru_cache(None)
    def dp(i, j):
      if i > j - 1:
        return True
      if s[i] == s[j - 1]:
        return dp(i + 1, j - 1)
      return False

    n = len(s)

    for i in range(n):
      for j in range(i, n):
        if dp(0, i) and dp(i, j) and dp(j, n):
          return True

    return False

Approach 2: Bottom-up

  • Time: $O(n^2)$
  • 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
class Solution {
 public:
  bool checkPartitioning(string s) {
    const int n = s.length();
    // dp[i][j] := true if s[i..j] is palindrome
    vector<vector<bool>> dp(n, vector<bool>(n));

    for (int i = 0; i < n; ++i)
      dp[i][i] = true;

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        if (s[i] == s[j])
          dp[i][j] = i + 1 > j - 1 || dp[i + 1][j - 1];
      }

    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j)
        if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1])
          return true;

    return false;
  }
};

 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 boolean checkPartitioning(String s) {
    final int n = s.length();
    // dp[i][j] := true if s[i..j] is palindrome
    boolean[][] dp = new boolean[n][n];

    for (int i = 0; i < n; ++i)
      dp[i][i] = true;

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        final int j = i + d;
        if (s.charAt(i) == s.charAt(j))
          dp[i][j] = i + 1 > j - 1 || dp[i + 1][j - 1];
      }

    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j)
        if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1])
          return true;

    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def checkPartitioning(self, s: str) -> bool:
    n = len(s)
    # dp[i][j] := true if s[i..j] is palindrome
    dp = [[False] * n for _ in range(n)]

    for i in range(n):
      dp[i][i] = True

    for d in range(1, n):
      for i in range(n - d):
        j = i + d
        if s[i] == s[j]:
          dp[i][j] = i + 1 > j - 1 or dp[i + 1][j - 1]

    for i in range(n):
      for j in range(i + 1, n):
        if dp[0][i] and dp[i + 1][j] and dp[j + 1][n - 1]:
          return True

    return False