You need to enable JavaScript to run this app. Java递归回文分区实现中内层List加入外层列表后输出为空问题
优惠活动
大模型
产品
解决方案
定价
更多

Java递归回文分区实现中内层List加入外层列表后输出为空问题

问题根因

这个空列表的问题本质是Java集合的引用传递特性导致的,也是回溯类算法最常踩的坑:

  • 整个递归流程中,你从main方法里只创建了1个ArrayList对象作为l1,所有递归分支全程共享这同一个对象
  • 当走到original.equals(p)的判断分支执行l2.add(l1)时,代码并不会把当前l1里的内容快照存进l2,只是把这个l1对象的内存引用追加到了结果集里
  • 等这个分支执行完回到上一层递归,你会执行回溯操作:l1.remove(l1.size()-1)删掉最后一个加进去的元素,这个修改是直接作用在那个已经被加进l2的l1对象上的
  • 所有递归流程跑完后,l1会在一次次的回溯删除操作下,回到最开始的空列表状态。而l2里存的所有元素,本质全指向这同一个最终被删空的l1对象,所以打印出来就是一堆嵌套空列表。

你在if分支里打印l1能看到正常内容,只是因为那个时间点刚好还没执行后续的回溯删除操作,等回溯流程走完,引用指向的对象已经被清空了,结果集里的内容自然就不对了。

修正方法

不要把原l1直接加进结果集,要存当前时刻l1内容的独立拷贝:
找到partition方法里的添加逻辑,把原来的

l2.add(l1);

改成

l2.add(new ArrayList<>(l1));

这行修改的作用是:创建一个全新的ArrayList对象,把当前l1里的所有元素逐份拷贝到这个新对象中,再把这个完全独立的新对象存进l2。后续你对原l1做的添加、删除回溯操作,不会对已经存进结果集的副本造成任何影响,每个符合条件的回文分区结果都会被独立保存,不会被后续的回溯操作篡改。

可优化的辅助逻辑
  • 循环里你对同一个i值重复调用了3次anotherGen(s,i),可以提前把生成的字符串存在局部变量里,减少重复计算的开销
  • 字符串p的回溯逻辑可以简化,不用每次都查找lastIndexOf截取子串,和l1的操作逻辑对齐即可

内容的提问来源于stack exchange,提问作者Mircia George

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.13 08:54:08