当前位置: 首页 > article >正文

剑指 Offer II 086. 分割回文子字符串


comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20086.%20%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2/README.md

剑指 Offer II 086. 分割回文子字符串

题目描述

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

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

 

示例 1:

输入:s = "google"
输出:[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]

示例 2:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 3:

输入:s = "a"
输出:[["a"] 

 

提示:

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

 

注意:本题与主站 131 题相同: https://leetcode.cn/problems/palindrome-partitioning/

解法

方法一:预处理 + DFS(回溯)

我们可以使用动态规划,预处理出字符串中的任意子串是否为回文串,即 f [ i ] [ j ] f[i][j] f[i][j] 表示子串 s [ i . . j ] s[i..j] s[i..j] 是否为回文串。

接下来,我们设计一个函数 d f s ( i ) dfs(i) dfs(i),表示从字符串的第 i i i 个字符开始,分割成若干回文串,当前分割方案为 t t t

如果 i = ∣ s ∣ i=|s| i=s,说明已经分割完成,我们将 t t t 放入答案数组中,然后返回。

否则,我们可以从 i i i 开始,从小到大依次枚举结束位置 j j j,如果 s [ i . . j ] s[i..j] s[i..j] 是回文串,那么就把 s [ i . . j ] s[i..j] s[i..j] 加入到 t t t 中,然后继续递归 d f s ( j + 1 ) dfs(j+1) dfs(j+1),回溯的时候要弹出 s [ i . . j ] s[i..j] s[i..j]

时间复杂度 O ( n × 2 n ) O(n \times 2^n) O(n×2n),空间复杂度 O ( n 2 ) O(n^2) O(n2)。其中 n n n 是字符串的长度。

Python3
# class Solution:
#     def partition(self, s: str) -> List[List[str]]:
#         def check(p):
#             l,r=0,len(p)-1
#             while l<r:
#                 if p[l]!=p[r]:
#                     return 0
#                 l,r=l+1,r-1
#             return 1

#         n=len(s)
#         res=[]
#         path=[]
#         def dfs(i,j): # 核心:边界的枚举
#             if i==n:
#                 res.append(path[:])
#                 return
            
#             for j in range(i,n):
#                 if not check(s[i:j+1]):continue
#                 path.append(s[i:j+1])
#                 dfs(j+1,j+1)
#                 path.pop()

#         dfs(0,0)
#         return res

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def check(path):
            l,r=0,len(path)-1
            while l<r:
                if path[l]!=path[r]:
                    return 0
                l,r=l+1,r-1
            return 1

        n=len(s)
        res=[]
        # path=[]
        def dfs(i,j,path): # 核心:边界的枚举
            if i==n:
                res.append(path[:])
                return
            
            for j in range(i,n):
                if not check(s[i:j+1]):continue
                # path.append(s[i:j+1]) #path,写不写在dfs里面都可以,写进去可以不用处理回溯
                dfs(j+1,j+1,path+[s[i:j+1]])
                # path.pop()

        dfs(0,0,[])
        return res
Java
class Solution {
    private int n;
    private String s;
    private boolean[][] f;
    private List<String> t = new ArrayList<>();
    private List<List<String>> ans = new ArrayList<>();

    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];
            }
        }
        this.s = s;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == s.length()) {
            ans.add(new ArrayList<>(t));
            return;
        }
        for (int j = i; j < n; ++j) {
            if (f[i][j]) {
                t.add(s.substring(i, j + 1));
                dfs(j + 1);
                t.remove(t.size() - 1);
            }
        }
    }
}
C++
class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        bool f[n][n];
        memset(f, true, sizeof(f));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = s[i] == s[j] && f[i + 1][j - 1];
            }
        }
        vector<vector<string>> ans;
        vector<string> t;
        function<void(int)> dfs = [&](int i) {
            if (i == n) {
                ans.push_back(t);
                return;
            }
            for (int j = i; j < n; ++j) {
                if (f[i][j]) {
                    t.push_back(s.substr(i, j - i + 1));
                    dfs(j + 1);
                    t.pop_back();
                }
            }
        };
        dfs(0);
        return ans;
    }
};
Go
func partition(s string) (ans [][]string) {
	n := len(s)
	f := make([][]bool, n)
	for i := range f {
		f[i] = make([]bool, n)
		for j := range f[i] {
			f[i][j] = true
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			f[i][j] = s[i] == s[j] && f[i+1][j-1]
		}
	}
	t := []string{}
	var dfs func(int)
	dfs = func(i int) {
		if i == n {
			ans = append(ans, append([]string(nil), t...))
			return
		}
		for j := i; j < n; j++ {
			if f[i][j] {
				t = append(t, s[i:j+1])
				dfs(j + 1)
				t = t[:len(t)-1]
			}
		}
	}
	dfs(0)
	return
}
TypeScript
function partition(s: string): string[][] {
    const n = s.length;
    const f: boolean[][] = new Array(n).fill(0).map(() => new Array(n).fill(true));
    for (let i = n - 1; i >= 0; --i) {
        for (let j = i + 1; j < n; ++j) {
            f[i][j] = s[i] === s[j] && f[i + 1][j - 1];
        }
    }
    const ans: string[][] = [];
    const t: string[] = [];
    const dfs = (i: number) => {
        if (i === n) {
            ans.push(t.slice());
            return;
        }
        for (let j = i; j < n; ++j) {
            if (f[i][j]) {
                t.push(s.slice(i, j + 1));
                dfs(j + 1);
                t.pop();
            }
        }
    };
    dfs(0);
    return ans;
}
C#
public class Solution {
    private int n;
    private string s;
    private bool[,] f;
    private IList<IList<string>> ans = new List<IList<string>>();
    private IList<string> t = new List<string>();

    public IList<IList<string>> Partition(string s) {
        n = s.Length;
        this.s = s;
        f = new bool[n, n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                f[i, j] = true;
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i, j] = s[i] == s[j] && f[i + 1, j - 1];
            }
        }
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == n) {
            ans.Add(new List<string>(t));
            return;
        }
        for (int j = i; j < n; ++j) {
            if (f[i, j]) {
                t.Add(s.Substring(i, j + 1 - i));
                dfs(j + 1);
                t.RemoveAt(t.Count - 1);
            }
        }
    }
}
Swift
class Solution {
    private var n: Int = 0
    private var s: String = ""
    private var f: [[Bool]] = []
    private var t: [String] = []
    private var ans: [[String]] = []

    func partition(_ s: String) -> [[String]] {
        n = s.count
        self.s = s
        f = Array(repeating: Array(repeating: true, count: n), count: n)

        let chars = Array(s)

        for i in stride(from: n - 1, through: 0, by: -1) {
            for j in i + 1 ..< n {
                f[i][j] = chars[i] == chars[j] && f[i + 1][j - 1]
            }
        }

        dfs(0)
        return ans
    }

    private func dfs(_ i: Int) {
        if i == n {
            ans.append(t)
            return
        }
        for j in i ..< n {
            if f[i][j] {
                t.append(String(s[s.index(s.startIndex, offsetBy: i)...s.index(s.startIndex, offsetBy: j)]))
                dfs(j + 1)
                t.removeLast()
            }
        }
    }
}

http://www.kler.cn/a/587384.html

相关文章:

  • Redis 的应用场景
  • MyBatis SqlSessionFactory 是如何创建的?
  • 什么是 slot-scope?怎么理解。
  • 组合Ⅲ 力扣216
  • 基于express+TS+mysql+sequelize的后端开发环境搭建
  • Go语言的移动应用测试
  • uniapp-x 子组件样式覆盖
  • 【推荐项目】052-用水监控管理系统
  • MAC地址IP地址如何转换?
  • 【Linux我做主】基础命令完全指南上篇
  • 从0到1构建AI深度学习视频分析系统--基于YOLO 目标检测的动作序列检查系统:(2)消息队列与消息中间件
  • SpringCloud系列教程(十四):Sentinel持久化
  • element 的tab怎么动态根据参数值添加一个vue页面
  • LeetCode 解题思路 17(Hot 100)
  • Android 自定义数字键盘实现教程
  • POCO F4刷机color 15
  • WSL2 Ubuntu安装GCC不同版本
  • 剑指 Offer II 087. 复原 IP
  • 计算机:基于深度学习的Web应用安全漏洞检测与扫描
  • kong搭建一套微信小程序的公司研发环境