极客教程在Java中对一个字符串进行万向排序
我们得到了一个字符串inStr。我们的任务是找到并打印出所有可能从字符串inStr中产生的宫廷排列。请注意，inStr中的所有字符都必须被用来生成回文。如果一个回文不存在，那么就显示一个适当的信息。
给定一个字符串，我们需要打印所有可以用该字符串的字母生成的可能的宫廷对联。例子。
例1 :
输入
字符串 inStr = “ttpkkp”
输出
“ptkktp”, “pkttkp”, “tpkkpt”, “tkppkt”, “kpttpk”, “ktpptk “是输入字符串的宫廷排列组合。
解释一下 。
这些是唯一包含了输入字符串inStr的所有字符的字符串，而且也是宫格的。
例2 :
输入
字符串inStr = “kkbbckdkd”
输出
“kkbdcdbkk” “kkdbcbdkk” “kbkdcdkbk” “kbdkckdbk” “kdkbcbkdk” “kdbkckbdk” “bkkdcdkkb” “bkdkckdkb” “bdkkckkdb” “dkkbcbkkd” “ddkbkckbkd” “dbkkckkbd”
解释一下 。
这些是唯一包含了输入字符串inStr的所有字符的字符串，而且也是回文。
例3 :
输入
字符串inStr = “kkb”
输出
“kbk”
解释一下 。
唯一的字符串 “kbk “包括输入字符串inStr中的所有字符，并且是一个回文。
简单的方法
简单的方法是找出字符串inStr的所有子集。然后，过滤掉那些大小与inStr相等的子集。在过滤出来的子集中，检查那些是复数的子集并打印出来。
文件名： PalindromePermutation.java
// importing HashSet, ArrayList, Iterator
// as they are required in the program
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Iterator;
public class PalindromePermutation
{
// a set that contains all the permutations
// of the string str1
HashSet hSet;
// permuting the string str1
private void permuteString(String str1, int lt, int rt)
{
// handling the base case
if (lt == rt)
{
// storing the permuted string str1
hSet.add(str1);
return;
}
else
{
// loop that does the permutation
for (int j = lt; j <= rt; j++)
{
str1 = strSwap(str1, lt, j);
permuteString(str1, lt + 1, rt);
str1 = strSwap(str1, lt, j);
}
}
}
// swapping the characters positioned at m and n
public String strSwap(String st1, int m, int n)
{
char t;
char[] charArr = st1.toCharArray();
t = charArr[m];
charArr[m] = charArr[n];
charArr[n] = t;
return String.valueOf(charArr);
}
// a method that checks whether the string str is
// a palindrome or not
public boolean isPalindrome(String str)
{
int i = 0;
int j = str.length() - 1;
while(i <= j)
{
// if the characters do not match, return false
// as the string str is not palindrome
if(str.charAt(i) != str.charAt(j))
{
return false;
}
i = i + 1;
j = j - 1;
}
return true;
}
//
public ArrayList palindromeStrings(String str)
{
// size of the input string str
int size = str.length();
permuteString(str, 0, size - 1);
// list that stores the permuted palindrome string
ArrayList ans = new ArrayList( );
// iterator for iterating over the hash set
Iterator itr = hSet.iterator();
while(itr.hasNext())
{
String temp = itr.next();
if(isPalindrome(temp))
{
// if the control comes here,
// then it means the string temp is a palindrome
// and should be added to the list
ans.add(temp);
}
}
return ans;
}
// main method
public static void main(String args[])
{
// creating an object of the class PalindromePermutation
PalindromePermutation obj = new PalindromePermutation();
String inStr = "ttpkkp"; // input 1
obj.hSet = new HashSet();
ArrayList list = obj.palindromeStrings(inStr);
System.out.println("For the string: " + inStr);
System.out.println("The permutated palindrome strings are: ");
for(int i = 0; i < list.size(); i++)
{
System.out.print(list.get(i) + " ");
}
System.out.println( "\n");
inStr = "kkbbckdkd"; // input 2
obj.hSet = new HashSet();
list = obj.palindromeStrings(inStr);
System.out.println("For the string: " + inStr);
System.out.println("The permutated palindrome strings are: ");
for(int i = 0; i < list.size(); i++)
{
System.out.print(list.get(i) + " ");
}
System.out.println( "\n");
inStr = "kkb"; // input 3
obj.hSet = new HashSet();
list = obj.palindromeStrings(inStr);
System.out.println("For the string: " + inStr);
System.out.println("The permutated palindrome string is: ");
for(int i = 0; i < list.size(); i++)
{
System.out.print(list.get(i) + " ");
}
}
}
输出 。
For the string: ttpkkp
The permutated palindrome strings are:
kpttpk tpkkpt ktpptk ptkktp pkttkp tkppkt
For the string: kkbbckdkd
The permutated palindrome strings are:
kbdkckdbk bdkkckkdb kkbdcdbkk kdkbcbkdk dkkbcbkkd kdbkckbdk bkkdcdkkb kbkdcdkbk dbkkckkbd kkdbcbdkk dkbkckbkd bkdkckdkb
For the string: kkb
The permutated palindrome string is:
kbk
复杂度分析： 该程序正在进行字符串的排列组合。该程序也在使用循环。然而，字符串的排列组合是主要的耗时过程，这使得程序的时间复杂度为O(n!)。另外，该程序使用哈希集来存储输入字符串的排列组合。因此，该程序的空间复杂度也是O(n! x n)，其中n是输入字符串中存在的字符总数。
在看了上述程序的复杂性分析后，显然需要进行一些优化。这是因为上述程序的复杂性很大。在编写程序之前，让我们看看下面的步骤。
第1步： 首先，需要检查使用输入字符串的字符是否可以生成一个宫格。如果不能生成宫格，则返回。
第2步：在做完第一步的检查后，我们可以通过考虑输入字符串中每个字符的一半频率来创建第一个宫锁链的一半部分（从词典上看是最小的）。
第3步： 现在遍历半数字符串的所有可能的排列组合，每次都在最后加上这部分的反面。
第4步： 如果字符串的长度是奇数，则在其间添加频率为奇数的字符，以形成宫格。
现在，请观察以下程序。
文件名： PalindromePermutation1.java
// importing HashSet, ArrayList, Iterator
// as they are required in the program
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Iterator;
public class PalindromePermutation1
{
// a set that contains all the permutation
// of the string str1
HashSet hSet;
// permuting the string st1
private void permuteString(String str1, int lt, int rt)
{
// handling the base case
if (lt == rt)
{
// storing the permuted string str1
hSet.add(str1);
return;
}
else
{
// loop that does the permutation
for (int j = lt; j <= rt; j++)
{
str1 = strSwap(str1, lt, j);
permuteString(str1, lt + 1, rt);
str1 = strSwap(str1, lt, j);
}
}
}
// swapping the characters positioned at m and n
public String strSwap(String st1, int m, int n)
{
char t;
char[] charArr = st1.toCharArray();
t = charArr[m];
charArr[m] = charArr[n];
charArr[n] = t;
return String.valueOf(charArr);
}
// A utility method for counting the frequencies and checking
// whether the character can make a palindrome or not
boolean isPalindrome(String str1, int freq[])
{
int len = str1.length();
// Updating frequency according to given string */
for (int j = 0; j < len; j++)
{
freq[str1.charAt(j) - 'a'] = freq[str1.charAt(j) - 'a'] + 1;
}
int oddFreq = 0;
// Loop for counting the total characters that have odd frequency
for (int j = 0; j < 26; j++)
{
if (freq[j] % 2 == 1)
{
oddFreq = oddFreq + 1;
}
}
// Condition for Palindrome:
// if the length is odd, then only one character frequency has to be odd
// if the length is even, then no character frequency has to be odd
if ((len % 2 == 1 && oddFreq == 1 ) || (len % 2 == 0 && oddFreq == 0))
{
return true;
}
else
{
return false;
}
}
// Utility method for reversing a string
String reverse(String str1)
{
String rev = "";
for (int j = 0; j < str1.length(); j++)
{
char ch = str1.charAt(j); // stores the character
rev= ch + rev; // add the character ch in the beginning of the existing string
}
return rev;
}
// method for printing all of the possible palindromes by characters of
// the input strings
public ArrayList palindromeStrings(String str)
{
int freq1[] = new int[26];
ArrayList ansList = new ArrayList();
// checking whether letter can make palindrome or not
if (!isPalindrome(str, freq1))
{
return ansList;
}
int len = str.length();
// half contains the half part of all the palindromes,
// It is the reason we are pushing the half freq of each
// of the letter
String halfStr = "";
char oddChar = '\0';
for (int i = 0; i < 26; i++)
{
// The condition will be true at most once
if(freq1[i] % 2 == 1)
{
oddChar = (char)(i + 'a');
}
String t = "";
for(int j = 0; j < freq1[i] / 2; j++)
{
t = t + (char)(i + 'a');
}
halfStr = halfStr + t;
}
permuteString(halfStr, 0, halfStr.length() - 1);
// palinStr keeps all possible palindromes
String palinStr = "";
// iterator for iterating over the hash set
Iterator itr = hSet.iterator();
// Now, iterating through all permutations of half and adding
// reverse part at the end.
// if the length is odd, then pushing oddCharacter also in mid
while(itr.hasNext())
{
String temp = itr.next();
palinStr = temp;
//System.out.println(reverse(temp));
if (len % 2 == 1)
{
palinStr = palinStr + oddChar;
}
palinStr = palinStr + reverse(temp);
ansList.add(palinStr);
}
return ansList;
}
// main method
public static void main(String args[])
{
// creating an object of the class PalindromePermutation1
PalindromePermutation1 obj = new PalindromePermutation1();
String inStr = "ttpkkp"; // input 1
obj.hSet = new HashSet();
ArrayList list = obj.palindromeStrings(inStr);
System.out.println("For the string: " + inStr);
System.out.println("The permutated palindrome strings are: ");
for(int i = 0; i < list.size(); i++)
{
System.out.print(list.get(i) + " ");
}
System.out.println( "\n");
inStr = "kkbbckdkd"; // input 2
obj.hSet = new HashSet();
list = obj.palindromeStrings(inStr);
System.out.println("For the string: " + inStr);
System.out.println("The permutated palindrome strings are: ");
for(int i = 0; i < list.size(); i++)
{
System.out.print(list.get(i) + " ");
}
System.out.println( "\n");
inStr = "kkb"; // input 3
obj.hSet = new HashSet();
list = obj.palindromeStrings(inStr);
System.out.println("For the string: " + inStr);
System.out.println("The permutated palindrome string is: ");
for(int i = 0; i < list.size(); i++)
{
System.out.print(list.get(i) + " ");
}
}
}
输出 。
For the string: ttpkkp
The permutated palindrome strings are:
ktpptk ptkktp pkttkp tkppkt kpttpk tpkkpt
For the string: kkbbckdkd
The permutated palindrome strings are:
dbkkckkbd kdbkckbdk kkbdcdbkk dkkbcbkkd kdkbcbkdk kbkdcdkbk bdkkckkdb bkkdcdkkb kbdkckdbk kkdbcbdkk bkdkckdkb dkbkckbkd
For the string: kkb
The permutated palindrome string is:
kbk
复杂度分析： 该程序正在对一半的字符串进行置换。这使得该程序的时间复杂度为O((n / 2)!)。此外，该程序使用哈希集来存储输入字符串的排列组合。因此，该程序的空间复杂度也是O((n / 2)! x n / 2)，其中n是输入字符串中存在的字符总数。