1745. Palindrome Partitioning IV

 一刷

Version #2 DP + pick up two indices from the string to split string into 3 parts - better version

第一步还是把isPalin[i][j]全部算出来

Time O(N^2)

Space O(N^2)

Runtime: 235 ms, faster than 34.45% of Java online submissions for Palindrome Partitioning IV.

Memory Usage: 68.3 MB, less than 25.84% of Java online submissions for Palindrome Partitioning IV.

class Solution {

    public boolean checkPartitioning(String s) {

        boolean[][] isPalin = new boolean[s.length() + 1][s.length() + 1];

        for (int end = 0; end < s.length(); end++) {

            for (int start = end; start >= 0; start--) {

                if (start == end) {

                    isPalin[start][end] = true;

                    continue;

                }

                isPalin[start][end] = s.charAt(start) == s.charAt(end) && (start + 1 >= end - 1 || isPalin[start + 1][end - 1]);

            }

        }

        // pick up 2 indices to split the string into [0, i)[i, j)[j, len)

        int len = s.length();

        for (int i = 1; i < len - 1; i++) {

            for (int j = i + 1; j < len; j++) {

                if (isPalin[0][i - 1] && isPalin[i][j - 1] && isPalin[j][len - 1]) {

                    return true;

                }

            }

        }

        return false;

    }

}

Version #1 General DP - Slower

这里没有利用到划分成3份的这个条件，而是将3当做了一个general的n

Time O(3 * N^2)

Space O(N^2)

Runtime: 312 ms, faster than 14.83% of Java online submissions for Palindrome Partitioning IV.

Memory Usage: 66.8 MB, less than 71.77% of Java online submissions for Palindrome Partitioning IV.

class Solution {

    public boolean checkPartitioning(String s) {

        boolean[][] isPalin = new boolean[s.length() + 1][s.length() + 1];

        for (int end = 0; end < s.length(); end++) {

            for (int start = end; start >= 0; start--) {

                if (start == end) {

                    isPalin[start][end] = true;

                    continue;

                }

                isPalin[start][end] = s.charAt(start) == s.charAt(end) && (start + 1 >= end - 1 || isPalin[start + 1][end - 1]);

            }

        }

        // dp[i] - If it's possible to split substring [0, i) into n palindroms

        boolean[] dp = new boolean[s.length() + 1];

        for (int n = 1; n <= 3; n++) {

            boolean[] currDP = new boolean[s.length() + 1];

            for (int i = 1; i <= s.length(); i++) {

                if (n == 1) {

                    // split substring [0, i - 1] into 1 partition

                    currDP[i] = isPalin[0][i - 1];

                    continue;

                }

                for (int j = i - 1; j >= n - 1; j--) {

                    currDP[i] = dp[j] && isPalin[j][i - 1];

                    if (currDP[i]) {

                        break;

                    }

                }

            }

            dp = currDP;

        }

        return dp[s.length()];

    }

}