Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Leetcode 131. Palindrome Partitioning #189

Open
Woodyiiiiiii opened this issue Jan 22, 2023 · 0 comments
Open

Leetcode 131. Palindrome Partitioning #189

Woodyiiiiiii opened this issue Jan 22, 2023 · 0 comments

Comments

@Woodyiiiiiii
Copy link
Owner

首先是想到用什么方法。

从题目出发,观察到数组长度小所有结果要呈现,所以想到直接使用回溯法如果是求个数,则考虑用DP

那么我第一次写了如下版本:

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtracking(res, new ArrayList<>(), s, 0, 0);
        return res;
    }

    private void backtracking(List<List<String>> res, List<String> list, String s, int start, int idx) {
        if (idx == s.length() || start == s.length()) {
            return;
        }
        // check if palindrome
        for (int i = idx; i < s.length(); ++i) {
            if (isPalindrome(s, start, i)) {
                list.add(s.substring(start, i + 1));
                if (i == s.length() - 1) {
                    res.add(new ArrayList<>(list));
                    return;
                }
                backtracking(res, new ArrayList<>(list), s, i + 1, i + 1);
                list.remove(list.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int start, int idx) {
        while (start < idx) {
            if (s.charAt(start) != s.charAt(idx)) {
                return false;
            }
            start++;
            idx--;
        }
        return true;
    }
}

这样能AC,但时间复杂度是O(N*2^N),有没有办法去优化时间复杂度呢?

回溯法很难绕开,那显然要优化判断Palindrome的函数,因为肯定有重复计算的部分。我们用boolean类型的dp[s.length()][s.length()]记录dp[i][j]表示i到j的子字符串是否是palindrome;判断条件是if (s.charAt(start) == s.charAt(i) && (i - start <= 1 || dp[start + 1][i - 1])) :

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); ++i) {
            dp[i][i] = true;
        }
        backtracking(res, new ArrayList<>(), s, dp, 0, 0);
        return res;
    }

    private void backtracking(List<List<String>> res, List<String> list, String s, boolean[][] dp, int start, int idx) {
        if (idx == s.length() || start == s.length()) {
            return;
        }
        // check if palindrome
        for (int i = idx; i < s.length(); ++i) {
            if (s.charAt(start) == s.charAt(i) && (i - start <= 1 || dp[start + 1][i - 1])) {
                dp[start][i] = true;
                list.add(s.substring(start, i + 1));
                if (i == s.length() - 1) {
                    res.add(new ArrayList<>(list));
                    return;
                }
                backtracking(res, new ArrayList<>(list), s, dp, i + 1, i + 1);
                list.remove(list.size() - 1);
            }
        }
    }
}

实际上时间复杂度还是没变。

Tips:
所以,dp[n][n]可以表示所有连续子字符串/子数组的关系,这点以后会有用。


Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant