Java 中的字符串回文排列

2024 年 9 月 10 日 | 阅读 8 分钟

我们得到了一个字符串 inStr。我们的任务是找出并打印出使用 inStr 字符串可以生成的所有回文。请注意，inStr 字符串的所有字符都必须用于生成回文。如果不存在回文，则显示适当的消息。

给定一个字符串，我们需要打印出可以使用该字符串中的字母生成的所有可能的 palindrome。示例：

示例 1

输入

字符串 inStr = "ttpkkp"

输出

"ptkktp", "pkttkp", "tpkkpt", "tkppkt", "kpttpk", "ktpptk" 是输入字符串的回文排列。

解释

这些是唯一包含了输入字符串 inStr 的所有字符并且也是回文的字符串。

示例 2

输入

字符串 inStr = "kkbbckdkd"

输出

"kkbdcdbkk" "kkdbcbdkk" "kbkdcdkbk" "kbdkckdbk" "kdkbcbkdk" "kdbkckbdk" "bkkdcdkkb" "bkdkckdkb" "bdkkckkdb" "dkkbcbkkd" "dkbkckbkd" "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<String> 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<String> 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<String> ans = new ArrayList<String>( );
   
   // iterator for iterating over the hash set
   Iterator<String> 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<String>();
  ArrayList<String> 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<String>();
  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<String>();
  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<String> 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<String> palindromeStrings(String str)
{
int freq1[] = new int[26];
ArrayList<String> ansList = new ArrayList<String>();

// 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<String> 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<String>();
ArrayList<String> 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<String>();
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<String>();
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 是输入字符串中存在的总字符数。

下一主题Grepcode java.util.Date

Java 中的字符串回文排列

简单方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的字符串回文排列

简单方法

相关帖子

Rotten Oranges Problem in Java

SortedSet add() method in Java with Examples

Java 中的确定赋值

Java 中的类定义

查找给定序列中不存在的最小正整数

Java 中编译时多态和运行时多态之间的区别

Java 中将 ArrayList 复制到另一个 ArrayList

Java 中的并行流与顺序流

Java 中的蝴蝶图案

Java NLP

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器