检查给定字符串的字符是否可以重新排列以形成回文

2021年4月1日15:22:54 发表评论 872 次浏览

本文概述

给定字符串, 请检查给定字符串的字符是否可以重新排列以形成回文。

例如, 可以将" geeksogeeks"的字符重新排列以形成回文" geeksoskeegeg", 但是不能将" lsbin"的字符重新排列以形成一个回文。

如果最多一个字符出现奇数次而所有字符出现偶数次, 则一组字符可以形成回文。

一个简单的解决方案是运行两个循环, 外循环一个接一个地拾取所有字符, 内循环计算被拾取字符的出现次数。我们跟踪奇数。该解决方案的时间复杂度为O(n2)。

我们可以使用count数组在O(n)时间内完成此操作。以下是详细步骤。

1)创建一个字母大小的计数数组, 通常为256。将计数数组的所有值初始化为0。

2)遍历给定的字符串和每个字符的递增计​​数。

3)遍历count数组, 如果count数组具有多个奇数, 则返回false。否则返回true。

下面是上述方法的实现。

C ++

// C++ implementation to check if
// characters of a given string can
// be rearranged to form a palindrome
#include<bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
   
/* function to check whether characters of a string can form 
    a palindrome */
bool canFormPalindrome(string str)
{
     // Create a count array and initialize all 
     // values as 0
     int count[NO_OF_CHARS] = {0};
   
     // For each character in input strings, // increment count in the corresponding
     // count array
     for ( int i = 0; str[i];  i++)
         count[str[i]]++;
   
     // Count odd occurring characters
     int odd = 0;
     for ( int i = 0; i < NO_OF_CHARS; i++)
     {
         if (count[i] & 1)
             odd++;
  
         if (odd > 1)
             return false ;
     }
   
     // Return true if odd count is 0 or 1, return true ;
}
   
/* Driver program*/
int main()
{
   canFormPalindrome( "lsbin" )? cout << "Yes\n" : 
                                      cout << "No\n" ;
   canFormPalindrome( "geeksogeeks" )? cout << "Yes\n" : 
                                     cout << "No\n" ;
   return 0;
}

Java

// Java implementation to check if
// characters of a given string can
// be rearranged to form a palindrome
import java.io.*;
import java.util.*;
import java.math.*;
  
class GFG {
  
static int NO_OF_CHARS = 256 ;
  
     /* function to check whether characters 
     of a string can form a palindrome */
     static boolean canFormPalindrome(String str) {
      
     // Create a count array and initialize all
     // values as 0
     int count[] = new int [NO_OF_CHARS];
     Arrays.fill(count, 0 );
  
     // For each character in input strings, // increment count in the corresponding
     // count array
     for ( int i = 0 ; i < str.length(); i++)
     count[( int )(str.charAt(i))]++;
  
     // Count odd occurring characters
     int odd = 0 ;
     for ( int i = 0 ; i < NO_OF_CHARS; i++) 
     {
     if ((count[i] & 1 ) == 1 )
         odd++;
  
     if (odd > 1 )
         return false ;
     }
  
     // Return true if odd count is 0 or 1, return true ;
}
  
// Driver program
public static void main(String args[])
{
     if (canFormPalindrome( "lsbin" ))
     System.out.println( "Yes" );
     else
     System.out.println( "No" );
  
     if (canFormPalindrome( "geeksogeeks" ))
     System.out.println( "Yes" );
     else
     System.out.println( "No" );
}
}
  
// This code is contributed by Nikita Tiwari.

Python3

# Python3 implementation to check if
# characters of a given string can
# be rearranged to form a palindrome
  
NO_OF_CHARS = 256
  
# function to check whether characters
# of a string can form a palindrome 
def canFormPalindrome(st) :
  
     # Create a count array and initialize  
     # all values as 0
     count = [ 0 ] * (NO_OF_CHARS)
  
     # For each character in input strings, # increment count in the corresponding
     # count array
     for i in range ( 0 , len (st)) :
         count[ ord (st[i])] = count[ ord (st[i])] + 1
  
     # Count odd occurring characters
     odd = 0
      
     for i in range ( 0 , NO_OF_CHARS ) :
         if (count[i] & 1 ) :
             odd = odd + 1
  
         if (odd > 1 ) :
             return False
              
     # Return true if odd count is 0 or 1, return True
  
# Driver program
if (canFormPalindrome( "lsbin" )) :
     print ( "Yes" )
else :
     print ( "No" )
      
if (canFormPalindrome( "geeksogeeks" )) :
     print ( "Yes" )
else :
     print ( "No" )
  
# This code is contributed by Nikita Tiwari.

C#

// C# implementation to check if
// characters of a given string can
// be rearranged to form a palindrome
  
using System;
   
class GFG {
   
static int NO_OF_CHARS = 256;
   
     /* function to check whether characters 
     of a string can form a palindrome */
     static bool canFormPalindrome( string str) {
       
     // Create a count array and initialize all
     // values as 0
     int [] count = new int [NO_OF_CHARS];
     Array.Fill(count, 0);
   
     // For each character in input strings, // increment count in the corresponding
     // count array
     for ( int i = 0; i < str.Length; i++)
     count[( int )(str[i])]++;
   
     // Count odd occurring characters
     int odd = 0;
     for ( int i = 0; i < NO_OF_CHARS; i++) 
     {
     if ((count[i] & 1) == 1)
         odd++;
   
     if (odd > 1)
         return false ;
     }
   
     // Return true if odd count is 0 or 1, return true ;
}
   
// Driver program
public static void Main()
{
     if (canFormPalindrome( "lsbin" ))
     Console.WriteLine( "Yes" );
     else
     Console.WriteLine( "No" );
   
     if (canFormPalindrome( "geeksogeeks" ))
     Console.WriteLine( "Yes" );
     else
     Console.WriteLine( "No" );
}
}

输出如下：

No
Yes

本文由Abhishek提供。如果发现任何不正确的地方, 或者你想分享有关上述主题的更多信息, 请发表评论

另一种方法：

我们可以使用列表在O(n)时间内完成此操作。以下是详细步骤。

1)创建一个字符列表。

2)遍历给定的字符串。

3)对于字符串中的每个字符, 如果列表中已经包含其他字符, 则删除该字符, 否则添加到列表中。

3)如果字符串长度为偶数, 则列表应该为空。

4)或如果字符串长度为奇数, 则列表大小应为1

5)在上述两个条件下(3)或(4)返回true, 否则返回false。

C ++

#include<bits/stdc++.h>
using namespace std;
  
/*
* function to check whether characters of 
a string can form a palindrome
*/
bool canFormPalindrome(string str)
{
  
     // Create a list
     vector< char > list;
  
     // For each character in input strings, // remove character if list contains
     // else add character to list
     for ( int i = 0; i < str.length(); i++)
     {
         auto pos = find(list.begin(), list.end(), str[i]);
         if (pos != list.end())
         {
             auto posi = find(list.begin(), list.end(), str[i]);
             list.erase(posi);
         }
         else
             list.push_back(str[i]);
     }
  
     // if character length is even list is expected to be empty
     // or if character length is odd list size is expected to be 1
     if (str.length() % 2 == 0 && list.empty() // if string length is even
         || (str.length() % 2 == 1 && list.size() == 1)) // if string length is odd
         return true ;
     else
         return false ;
  
}
  
// Driver program
int main() 
{
     if (canFormPalindrome( "lsbin" ))
         cout << ( "Yes" ) << endl;
     else
         cout << ( "No" ) << endl;
  
     if (canFormPalindrome( "geeksogeeks" ))
         cout << ( "Yes" ) << endl;
     else
         cout << ( "No" ) << endl;
}
  
// This code is contributed by Rajput-Ji

Java

import java.util.ArrayList;
import java.util.List;
  
class GFG{
  
     /*
      * function to check whether characters of a string can form a palindrome
      */
     static boolean canFormPalindrome(String str) {
  
         // Create a list
         List<Character> list = new ArrayList<Character>();
  
         // For each character in input strings, // remove character if list contains
         // else add character to list
         for ( int i = 0 ; i < str.length(); i++) {
             if (list.contains(str.charAt(i)))
                 list.remove((Character) str.charAt(i));
             else
                 list.add(str.charAt(i));
         }
  
         // if character length is even list is expected to be empty
         // or if character length is odd list size is expected to be 1
         if (str.length() % 2 == 0 && list.isEmpty() // if string length is even
                 || (str.length() % 2 == 1 && list.size() == 1 )) // if string length is odd
             return true ;
         else
             return false ;
  
     }
  
     // Driver program
     public static void main(String args[]) {
         if (canFormPalindrome( "lsbin" ))
             System.out.println( "Yes" );
         else
             System.out.println( "No" );
  
         if (canFormPalindrome( "geeksogeeks" ))
             System.out.println( "Yes" );
         else
             System.out.println( "No" );
     }
}
  
// This code is contributed by Sugunakumar P

Python3

'''
* function to check whether characters of 
a strring can form a palindrome
'''
def canFormPalindrome(strr):
      
     # Create a listt
     listt = []
      
     # For each character in input strrings, # remove character if listt contains
     # else add character to listt
     for i in range ( len (strr)):
         if (strr[i] in listt):
             listt.remove(strr[i])
         else :
             listt.append(strr[i])
              
     # if character length is even listt is expected to be empty
     # or if character length is odd listt size is expected to be 1
     if ( len (strr) % 2 = = 0 and len (listt) = = 0 or \
         ( len (strr) % 2 = = 1 and len (listt) = = 1 )):
         return True
     else :
         return False
  
# Driver code
if (canFormPalindrome( "lsbin" )):
     print ( "Yes" )
else :
     print ( "No" )
      
if (canFormPalindrome( "geeksogeeks" )):
     print ( "Yes" )
else :
     print ( "No" )
  
# This code is contributed by SHUBHAMSINGH10

C#

// C# Implementation of the above approach 
using System; 
using System.Collections.Generic;
class GFG
{
  
     /*
     * function to check whether characters 
       of a string can form a palindrome
     */
     static Boolean canFormPalindrome(String str) 
     {
  
         // Create a list
         List< char > list = new List< char >();
  
         // For each character in input strings, // remove character if list contains
         // else add character to list
         for ( int i = 0; i < str.Length; i++) 
         {
             if (list.Contains(str[i]))
                 list.Remove(( char ) str[i]);
             else
                 list.Add(str[i]);
         }
  
         // if character length is even
         // list is expected to be empty
         // or if character length is odd 
         // list size is expected to be 1
         if (str.Length % 2 == 0 && list.Count == 0 || // if string length is even
            (str.Length % 2 == 1 && list.Count == 1)) // if string length is odd
             return true ;
         else
             return false ;
  
     }
  
     // Driver Code
     public static void Main(String []args) 
     {
         if (canFormPalindrome( "lsbin" ))
             Console.WriteLine( "Yes" );
         else
             Console.WriteLine( "No" );
  
         if (canFormPalindrome( "geeksogeeks" ))
             Console.WriteLine( "Yes" );
         else
             Console.WriteLine( "No" );
     }
}
  
// This code is contributed by Rajput-Ji

输出如下：

No
Yes
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: