输出中子串位移的回文分割问题的回溯解决方案

Question

我正在解决palindrome partitioning on Leetcode的问题。

我已经编写了一个递归解决方案，它打印出正确的子字符串列表，但是对于其中一个测试用例，列表中的顺序与预期输出不匹配。

输入：

cbbbcc

输出：

[["c","b","b","b","c","c"],["b","b","b","c","cc"],["b","c","bb","c","c"],["b","bb","c","cc"],["c","bb","b","c","c"],["bb","b","c","cc"],["c","bbb","c","c"],["bbb","c","cc"],["cbbbc","c"]]

预期：

[["c","b","b","b","c","c"],["c","b","b","b","cc"],["c","b","bb","c","c"],["c","b","bb","cc"],["c","bb","b","c","c"],["c","bb","b","cc"],["c","bbb","c","c"],["c","bbb","cc"],["cbbbc","c"]]

我无法弄清楚为什么我的递归调用会移动此示例中的第一个元素 "c"。

public class Solution {

public List<List<String>> partition(String s) {

    List<List<String>> result = new ArrayList<>();
    backTrack(result, new ArrayList<String>(), s);

    return result;
}

private void backTrack(List<List<String>> result, List<String> cur, String s){

    if(s.length() == 0)
        result.add(new ArrayList<>(cur));

    /* length = i+1 */
    for(int i = 0; i < s.length(); i++){
        if(isPalindrome(s.substring(0, i+1))){
            cur.add(s.substring(0, i+1));
            backTrack(result, cur, s.substring(i+1, s.length()));
            cur.remove(s.substring(0, i+1));
        }
    }

}

private boolean isPalindrome(String s){
    int start = 0, end = s.length() - 1;
    char[] schars = s.toCharArray();

    while(start < end){
        if(schars[start] != schars[end])
            return false;
        start++;
        end--;
    }
    return true;
}
}

我确实看过一个例子，按照我的逻辑，我看不出有任何理由应该像输出中那样替换 "c"。

Answer 1

问题是因为您期望 add 和 remove 与您的列表一起工作的方式。

最初，您从 s 构建 cur（此处 cbbbcc）：

s           cur
1. cbbbcc   []
2. bbbcc    [c]
3. bbcc     [c, b]
4. bcc      [c, b, b]
5. cc       [c, b, b, b]
6. c        [c, b, b, b, c]
7.          [c, b, b, b, c, c]

现在，以相反的顺序调用 backTrack() return 7、6、5...

因此，这一行：

cur.remove(s.substring(0, i+1));

首先是运行子字符串 "c".

理想情况下，您的代码应该从 cur 中删除最右边的 "c"。但是 remove 方法删除了它遇到的第一个 "c"，它位于位置 0。从这里开始，您的顺序总是错误的。

最简单的解决方案是始终添加到第一个位置以匹配 remove() 的默认行为。不过，在以这种方式使用之前，您需要反转字符串。

我已经在此处适当地修改了您的代码：

import java.util.*;
import java.lang.*;

public class Solution {

  public List<List<String>> partition(String s) {

      List<List<String>> result = new ArrayList<>();
      backTrack(result, new ArrayList<String>(), new StringBuilder(s).reverse().toString());  // EDIT 1: Invert String

      return result;
  }

  private void backTrack(List<List<String>> result, List<String> cur, String s) {
      if(s.length() == 0) result.add(new ArrayList<>(cur));

      for(int i = 0; i < s.length(); i++){
          if(isPalindrome(s.substring(0, i+1))){
              cur.add(0, s.substring(0, i+1)); // EDIT 2: Add to beginning of list
              backTrack(result, cur, s.substring(i+1, s.length()));
              cur.remove(s.substring(0, i+1));
          }
      }
  }

  private boolean isPalindrome(String s) {
      int start = 0, end = s.length() - 1;
      char[] schars = s.toCharArray();

      while(start < end){
          if(schars[start] != schars[end])
              return false;
          start++;
          end--;
      }
      return true;
  }
}

您可以运行在线 here 或以下。

<script src="//repl.it/embed/JNx4/0.js"></script>

或者，您可以通过查找列表中最右边出现的字符来简单地删除 ()，而不是反转字符串并添加到列表的左侧。

Answer 2

是的，似乎您要删除最左边的元素而不是最右边的元素 element.The 以下内容应该足够了：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class OneSolution {


private List<List<String>> partition(String s) {

    List<List<String>> result = new ArrayList<>();
    backTrack(result, new ArrayList<String>(), s);

    return result;
}

private void backTrack(List<List<String>> result, List<String> cur, String s) {
    if (s.length() == 0)
        result.add(new ArrayList<>(cur));

    for (int i = 0; i < s.length() && s.length() > 0; i++) {
        if (isPalindrome(s.substring(0, i + 1))) {
            cur.add(s.substring(0, i + 1));
            backTrack(result, cur, s.substring(i + 1, s.length()));
            Collections.reverse(cur);  //Reverse String remove 1st element
            cur.remove(s.substring(0, i + 1));
            Collections.reverse(cur);  //Reverse back to original
        }
    }

}

private boolean isPalindrome(String s) {
    StringBuilder stringBuilder = new StringBuilder(s);
    String rev = stringBuilder.reverse().toString();
    return rev.equals(s);
}

public static void main(String[] args) {
    OneSolution os = new OneSolution();
    System.out.println(os.partition("cbbbcc"));
    System.out.println(os.partition("bab"));
}

}

Verify

输出中子串位移的回文分割问题的回溯解决方案

Backtracking solution for palindrome partitioning issue with displacement of sub-string in the output

java

string

recursion

backtracking