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
相关产品推荐
相关产品推荐

