回文排列 II:别再傻傻地全排列了,剪枝才是王道
大家好,我是Echo_Wish。
今天咱们聊一道看起来是“字符串 + 回溯”的老题,但一不小心就会把 CPU 跑冒烟的经典问题——
回文排列 II(Palindrome Permutation II)。
这道题我特别喜欢,因为它非常适合用来区分“会写代码”和“会写算法”的差别。
一、先把问题说人话(别一上来就回溯)
题目大意是这样的:
给你一个字符串
s,请你返回所有不重复的回文排列。
注意几个关键词:
- 所有
- 不重复
- 回文
举个例子:
输入: "aabb" 输出: ["abba", "baab"]如果你第一反应是:
“我先全排列,再判断是不是回文?”
那我只能说一句老实话:
兄弟,你这是在给回溯