日韩无码传媒,中国学生妹黄色一级片免费看,再拍偷拍成人视频,青娱乐精品盛宴,国产字幕在线观看,亚洲欧美性爱视频,曰韩无码电影,黄色免费看

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問(wèn)題叫做?分割回文串，我們先來(lái)看題面：

https://leetcode-cn.com/problems/palindrome-partitioning/

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

題意

給定一個(gè)字符串 s，將 s 分割成一些子串，使每個(gè)子串都是回文串。

返回 s 所有可能的分割方案。

樣例


示例:

輸入: "aab"
輸出:
[
??["aa","b"],
??["a","a","b"]
]

解題

https://www.jianshu.com/p/e1017e1674ea

這是一道很綜合的題目，結(jié)合了動(dòng)態(tài)規(guī)劃，深度搜索和回溯法。

首先為了分割出回文串，我們首先要寫(xiě)出判斷回文串的方法，這里使用動(dòng)態(tài)規(guī)劃來(lái)判斷回文串，而且可以存儲(chǔ)子串的回文串的情況。

isPalindrome[i][j]:表示i到j(luò)的子串是否是回文串。

狀態(tài)轉(zhuǎn)移方程：

isPalindrome[i][j] = isPalindrome[i+1][j-1] && s.charAt(i) == s.charAt(j)

自然如果一個(gè)串是回文串，那么首尾必須要相等，并且中間也是子串。

初始化，顯然當(dāng)i==j的時(shí)候都是回文串

當(dāng)串只有兩個(gè)字符且相等的時(shí)候也是回文串。

知道如何判斷子串是否是回文串就好辦了，然后只要模式化的深度搜索回溯即可。

public?class?Solution?{
????/**
?????* @param s: A string
?????* @return: A list of lists of string
?????*/
????
????List> results;
????boolean[][] isPalindrome;
????
????/**
?????* @param s: A string
?????* @return: A list of lists of string
?????*/
????public?List> partition(String s) {
????????results = new?ArrayList<>();
????????if?(s == null?|| s.length() == 0) {
????????????return?results;
????????}
????????
????????getIsPalindrome(s);
????????
????????helper(s, 0, new?ArrayList());
????????
????????return?results;
????}
????
????private?void?getIsPalindrome(String s) {
????????int?n = s.length();
????????isPalindrome = new?boolean[n][n];
????????
????????for?(int?i = 0; i < n; i++) {
????????????isPalindrome[i][i] = true;
????????}
????????for?(int?i = 0; i < n - 1; i++) {
????????????isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
????????}
????????
????????for?(int?i = n - 3; i >= 0; i--) {
????????????for?(int?j = i + 2; j < n; j++) {
????????????????isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
????????????}
????????}
????}
????
????private?void?helper(String s,
????????????????????????int?startIndex,
????????????????????????List partition) {
????????if?(startIndex == s.length()) {
????????????addResult(s, partition);
????????????return;
????????}
????????
????????for?(int?i = startIndex; i < s.length(); i++) {
????????????if?(!isPalindrome[startIndex][i]) {
????????????????continue;
????????????}
????????????partition.add(i);
????????????helper(s, i + 1, partition);
????????????partition.remove(partition.size() - 1);
????????}
????}
????
????private?void?addResult(String s, List partition) {
????????List result = new?ArrayList<>();
????????int?startIndex = 0;
????????for?(int?i = 0; i < partition.size(); i++) {
????????????result.add(s.substring(startIndex, partition.get(i) + 1));
????????????startIndex = partition.get(i) + 1;
????????}
????????results.add(result);
????}
}