当前位置:   article > 正文

回溯——131. 分割回文串_leetcode分割回文串,记忆化搜索时间复杂度

leetcode分割回文串,记忆化搜索时间复杂度

1 题目描述

  1. 分割回文串
    给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/palindrome-partitioning

2 题目示例

示例 1:
输入:s = “aab”
输出:[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2:
输入:s = “a”
输出:[[“a”]]

3 题目提示

1 <= s.length <= 16
s 仅由小写英文字母组成

4 思路

方法一:回溯 + 动态规划预处理
由于需要求出字符串s的所有分割方案,因此我们考虑使用搜索+回溯的方法枚举所有可能的分割方法并进行判断。
假设我们当前搜索到字符串的第i个字符,且s[0…i-1]位置的所有字符已经被分割成若干个回文串,并且分割结果被放入了答案数组ans中,那么我们就需要枚举下一个回文串的右边界j,使得s[i…j]是一个回文串。
因此,我们可以从i开始,从小到大依次枚举j。对于当前枚举的j值,我们使用双指针的方法判断s[i…j]是否为回文串:如果s[i…j]是回文串,那么就将其加入答案数组ans中,并以j+1作为新的à进行下一层搜索,并在未来的回溯时将s[i…j]从ans中移除。
如果我们已经搜索完了字符串的最后一个字符,那么就找到了—种满足要求的分割方法。
复杂度分析
时间复杂度:o(n 2²),其中n是字符串s的长度。在最坏情况下,s包含n个完全相同的字符,因此它的任意—种划分方法都满足要求。而长度为n的字符串的划分方案数为2n-1= o(2²),每一种划分方法需要O(n)的时间求出对应的划分结果并放入答案,因此总时间复杂度为o(n·2²)。尽管动态规划预处理需要o(n²)的时间,但在渐进意义下小于O(n2²),因此可以忽略。
·空间复杂度:O(n²),这里不计算返回答案占用的空间。数组f需要使用的空间为O(n2),而在回溯的过程中,我们需要使用O(n)的栈空间以及O(n)的用来存储当前字符串分割方法的空间。由于O(n)在渐进意义下小于o(n²),因此空间复杂度为O(n²)。

方法二:回溯 + 记忆化搜索
方法一中的动态规划预处理计算出了任意的s[i…j]是否为回文串,我们也可以将这—步改为记忆化搜索。
复杂度分析

  • 时间复杂度:O(n ﹒ 2²),其中n是字符串s的长度,与方法一相同。
  • 空间复杂度:o(n²),与方法—相同。

5 我的答案

方法一:回溯 + 动态规划预处理

class Solution {
    boolean[][] f;
    List<List<String>> ret = new ArrayList<List<String>>();
    List<String> ans = new ArrayList<String>();
    int n;

    public List<List<String>> partition(String s) {
        n = s.length();
        f = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(f[i], true);
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
            }
        }

        dfs(s, 0);
        return ret;
    }

    public void dfs(String s, int i) {
        if (i == n) {
            ret.add(new ArrayList<String>(ans));
            return;
        }
        for (int j = i; j < n; ++j) {
            if (f[i][j]) {
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }
}
  • 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
  • 33
  • 34
  • 35
  • 36
  • 37

方法二:回溯 + 记忆化搜索

class Solution {
    int[][] f;
    List<List<String>> ret = new ArrayList<List<String>>();
    List<String> ans = new ArrayList<String>();
    int n;

    public List<List<String>> partition(String s) {
        n = s.length();
        f = new int[n][n];

        dfs(s, 0);
        return ret;
    }

    public void dfs(String s, int i) {
        if (i == n) {
            ret.add(new ArrayList<String>(ans));
            return;
        }
        for (int j = i; j < n; ++j) {
            if (isPalindrome(s, i, j) == 1) {
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }

    // 记忆化搜索中,f[i][j] = 0 表示未搜索,1 表示是回文串,-1 表示不是回文串
    public int isPalindrome(String s, int i, int j) {
        if (f[i][j] != 0) {
            return f[i][j];
        }
        if (i >= j) {
            f[i][j] = 1;
        } else if (s.charAt(i) == s.charAt(j)) {
            f[i][j] = isPalindrome(s, i + 1, j - 1);
        } else {
            f[i][j] = -1;
        }
        return f[i][j];
    }
}
  • 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
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/676720
推荐阅读
相关标签
  

闽ICP备14008679号