问题描述:
求解一个字符串中字符的全排列。
如:给定字符串”abc“
求出全排列: abc, acb, bac, bca, cad, cba
思路:
这道题排列不是问题,问题是方法不对会导致结果有重复元素。如果不能够一次性不重复排列,则会在去重上大费功夫。
这个问题我们不难想到,与“青蛙跳台阶”、“斐波那契数列”等问题解决方法有异曲同工之妙,仔细看来,这个问题也是可以划分为子问题,解决子问题进而逐步解决整体。但是,什么是子问题呢?
举个例子,我们用输入字符串 “abcd” 来说明:
(1)我们要求abcd的全排列,就可以分别以 a, b, c, d 开头,然后求 bcd, acd, bad, bca 的全排列。
(2)循环求上述四种情况,对于其中之一 a开头,后接bcd的情况,又可以对子串”bcd“进行(1)操作——即求bcd全排列。
(3)直到子问题级别到达只剩一个子串的全排列时候,就可以递归返回上一层了。
解决方法 – java代码:
public class 字符串的排列 {
public static List
运行结果:
abcd – abdc – acbd – acdb – adcb – adbc – bacd – badc – bcad – bcda – bdca – bdac – cbad – cbda – cabd – cadb – cdab – cdba – dbca – dbac – dcba – dcab – dacb – dabc –
其他文章
- 由遥控车引起的不可靠的消息服务(监听断连、顺序颠倒、消息丢失)的问题及解决背景:最近的项目中,有一个端到端控制的场景(即A发送命令,通过RTC服[…]
- Red Dead Redemption 2: 永远的亚瑟 · 摩根Red Dead Redemption 2 是一个致敬西部牛[…]
- 分享如何低成本DIY组装一台显示器相信有许多动手能力强的朋友,你是否想组装一台属于自己的独一无二的显示器呢?笔者下面分享一下Diy显示器的过程。文中也有一些对于显示器参数的拙见以及显示器最终的测试方式。
- OBS录制全屏黑屏解决方法问题描述:在使用OBS进行录屏时候,只能录制特定窗口,当选屏幕录制时候[…]
- 浅谈ArrayList源码实现本文记录笔者对JDK1.8下ArrayList源码的解读 ArrayL[…]
非常有用!