免费网站推广怎么做,下列不属于网站开发技术的是,网站开发转软件开发,自己可以制作微信小程序吗leetcode 131. 分割回文串
题目
给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1#xff1a;
输入#xff1a;s “aab” 输出#xff1a;[[“…leetcode 131. 分割回文串
题目
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1
输入s “aab” 输出[[“a”,“a”,“b”],[“aa”,“b”]] 示例 2
输入s “a” 输出[[“a”]]
提示
1 s.length 16 s 仅由小写英文字母组成
思路
这题说实话一开始合计的是一个个加进来然后当前最后一个字符串加上新的字符是回文串就继续dfs然后不管最后一个字符串加上新的字符是不是回文串这里都要断开。这样就能保证所有情况的覆盖因此有了第一版代码。但这WA了。。。因为没考虑所谓回文串aba是回文串新的字符是c可能不是回文串但再往后加可能是abacaba这又是回文串了。所以我们得考虑这种情况。于是有了第二版AC了。看了剪枝操作有了第三版不用每次都判断回文串了而是用一个数组存储各种情况在本题中最长就16字符所以效果不明显之后这种空间换时间的思路还是要记得的。
题解
// 第一版
class Solution {ListListString list new ArrayList();ListString subList new ArrayList();boolean st[];public ListListString partition(String s) {st new boolean[s.length()];dfs(s, 0);return list;}public boolean isOk(String item, char i) {if (item.charAt(0) ! i) {return false;}int st 1, ed item.length() - 1;while (st ed) {if (item.charAt(st) ! item.charAt(ed)) {return false;}st;ed--;}return true;}public boolean gap(int idx) {for (int iidx-1;i-1;i--) {if (st[i] false) {return true;}}return false;}public void dfs(String s, int idx) {if (idx s.length()) {list.add(new ArrayList(subList));return;}for (int iidx;is.length();i) {if (gap(i)) {return;}if (subList.isEmpty()){subList.add(String.valueOf(s.charAt(i)));st[i] true;dfs(s, i 1);subList.remove(0);st[i] false;}else if (isOk(subList.get(subList.size() - 1), s.charAt(i))) {String tmp subList.get(subList.size() - 1);subList.remove(subList.size() - 1);subList.add(tmp String.valueOf(s.charAt(i)));st[i] true;dfs(s, i 1);subList.remove(subList.size() - 1);subList.add(tmp);st[i] false;}if (! subList.isEmpty()) {subList.add(String.valueOf(s.charAt(i)));st[i] true;dfs(s, i 1);subList.remove(subList.size() - 1);st[i] false;}}}
}
// 第二版
class Solution {ListListString list new ArrayList();ListString subList new ArrayList();public ListListString partition(String s) {dfs(s, 0);return list;}public boolean isOk(String item) {int st 0, ed item.length() - 1;while (st ed) {if (item.charAt(st) ! item.charAt(ed)) {return false;}st;ed--;}return true;}public void dfs(String s, int idx) {if (idx s.length()) {list.add(new ArrayList(subList));return;}for (int iidx;is.length();i) {String str s.substring(idx, i 1);if (isOk(str)) {subList.add(str);dfs(s, i 1);subList.remove(subList.size() - 1);}else {continue;}}}
}
// 第三版
class Solution {ListListString list new ArrayList();ListString subList new ArrayList();// 空间换时间boolean[][] isPartition;public ListListString partition(String s) {isPartition new boolean[s.length()][s.length()];isOk(s);dfs(s, 0);return list;}public void isOk(String item) {for (int i0;iitem.length();i) {for (int ji;jitem.length();j) {int st i, ed j;while (st ed) {if (item.charAt(st) ! item.charAt(ed)) {break;}st;ed--;}if (st ed) {isPartition[i][j] true;}}} }public void dfs(String s, int idx) {if (idx s.length()) {list.add(new ArrayList(subList));return;}for (int iidx;is.length();i) {// 基于当前subList已有的回文串以及当前idx开始往后i - idx位只要有回文串就放里if (isPartition[idx][i]) {String str s.substring(idx, i 1);subList.add(str);dfs(s, i 1);subList.remove(subList.size() - 1);}else {continue;}}}
}
