生成给定字符串的所有排列 [英] Generating all permutations of a given string
问题描述
找到一个字符串的所有排列的优雅方法是什么?例如.ba
的置换,将是 ba
和 ab
,但是对于诸如 abcdefgh
这样的更长的字符串呢?有没有Java实现的例子?
What is an elegant way to find all the permutations of a string. E.g. permutation for ba
, would be ba
and ab
, but what about longer string such as abcdefgh
? Is there any Java implementation example?
推荐答案
这是我的解决方案,基于《破解编码面试》(P54)一书的想法:
Here is my solution that is based on the idea of the book "Cracking the Coding Interview" (P54):
/**
* List permutations of a string.
*
* @param s the input string
* @return the list of permutations
*/
public static ArrayList<String> permutation(String s) {
// The result
ArrayList<String> res = new ArrayList<String>();
// If input string's length is 1, return {s}
if (s.length() == 1) {
res.add(s);
} else if (s.length() > 1) {
int lastIndex = s.length() - 1;
// Find out the last character
String last = s.substring(lastIndex);
// Rest of the string
String rest = s.substring(0, lastIndex);
// Perform permutation on the rest string and
// merge with the last character
res = merge(permutation(rest), last);
}
return res;
}
/**
* @param list a result of permutation, e.g. {"ab", "ba"}
* @param c the last character
* @return a merged new list, e.g. {"cab", "acb" ... }
*/
public static ArrayList<String> merge(ArrayList<String> list, String c) {
ArrayList<String> res = new ArrayList<>();
// Loop through all the string in the list
for (String s : list) {
// For each string, insert the last character to all possible positions
// and add them to the new list
for (int i = 0; i <= s.length(); ++i) {
String ps = new StringBuffer(s).insert(i, c).toString();
res.add(ps);
}
}
return res;
}
<小时>
运行字符串abcd"的输出:
Running output of string "abcd":
步骤 1:合并 [a] 和 b:[ba, ab]
Step 1: Merge [a] and b: [ba, ab]
第 2 步:合并 [ba, ab] 和 c:[cba,bca,bac,cab,acb,abc]
Step 2: Merge [ba, ab] and c: [cba, bca, bac, cab, acb, abc]
第三步:合并[cba, bca, bac, cab, acb, abc]和d:[dcba,cdba,cbda,cbad,dbca,bdca,bcda,bcad,dbac,bdac,badc,bacd,dcab,cdab,cadb,cabd,dacb,adcb,acdb,acbd,dabc,adbc,abdc,abcd]
Step 3: Merge [cba, bca, bac, cab, acb, abc] and d: [dcba, cdba, cbda, cbad, dbca, bdca, bcda, bcad, dbac, bdac, badc, bacd, dcab, cdab, cadb, cabd, dacb, adcb, acdb, acbd, dabc, adbc, abdc, abcd]
这篇关于生成给定字符串的所有排列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!