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

Question

我正在解决Leetcode 上的回文分区问题。

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

输入：

bbbbcc

输出：

[["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

问题在于您对List 的期望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()相反的顺序返回的调用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;
  }
}

你可以在这里或下面在线运行。

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]

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