Cracking the coding interview--Q8.4

题目

原文:

Write a method to compute all permutations of a string.

译文:

写一个方法返回一个字符串的所有排列。

解答

显然对于一个长度为n的串,它的全排列共有A(n, n)=n!种,由递归的方法解,若字符串是“abc”,函数名为recursionPermu,由不同的递归思路分析。

解法一:

将第0个字符a取出,递归调用recursionPermu求出剩余串"bc"的所有排列,为"bc","cb",再分别针对此字符串进行插空得到全部排列:abc,bac,bca,acb,cab,cba,代码如下:

public static LinkedList recursionPermu(String str){ LinkedList result=new LinkedList(); if(str.equals("")){ result.add(""); return result; } String c=str.substring(0,1); LinkedList res=recursionPermu(str.substring(1)); for(int i=0;i
解法二:

另外可以依次取字符串的每个字符,然后用recursionPermu递归求出剩余串的排列数,再在每个排列前加上该字符即可,如abc的所有排列:abc,acb,bac,bca,cab,cba,代码如下:

public static LinkedList recursionPermu1(String str){ LinkedList result=new LinkedList(); if(str.equals("")){ result.add(""); return result; } for(int i=0;i res=recursionPermu1(eraseStr(t,i)); for(int j=0;j
完整代码如下:

import java.util.LinkedList; class Q8_4{ public static LinkedList recursionPermu(String str){ LinkedList result=new LinkedList(); if(str.equals("")){ result.add(""); return result; } String c=str.substring(0,1); LinkedList res=recursionPermu(str.substring(1)); for(int i=0;i recursionPermu1(String str){ LinkedList result=new LinkedList(); if(str.equals("")){ result.add(""); return result; } for(int i=0;i res=recursionPermu1(eraseStr(t,i)); for(int j=0;j res=recursionPermu(s); for(int i=0;i res1=recursionPermu1(s); for(int i=0;i
---EOF---

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:ZJU3723 状压DP
下一篇:URAL 1183 Brackets Sequence 记忆化搜索 + DFS
相关文章

Cracking the coding interview:

Cracking the coding interview--Q9.3

Cracking the coding interview--Q12.4

C++从零开始(三)何谓变量

如何用C++编程获得某台机器的IP地址?

C++辨析系列谈

利齿C sharp代替C++?

C++对象计数

C++中的 static 关键字

C/C++作用域引申出的编码规范

图文推荐

Cracking the coding interview--Q8.4
ZOJ 3640 Help Me
Cracking the coding interview--Q8.4
CF 518C(Anya and
Cracking the coding interview--Q8.4
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-03-14 人气:4
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.087 (s). 10 q(s)