算法题：检查两个字符串是否互为字谜

2021年4月18日19:07:38 发表评论 773 次浏览

本文概述

编写函数以检查两个给定的字符串是否为字谜彼此之间。字符串的字谜是另一个包含相同字符的字符串, 只有字符顺序可以不同。例如, " abcd"和" dabc"是彼此的字谜。

检查两个字符串是否互为字谜

方法1(使用排序)

  1. 对两个字符串进行排序
  2. 比较排序的字符串

以下是上述想法的实现：

C ++

//C++ program to check whether two strings are anagrams
//of each other
#include <bits/stdc++.h>
using namespace std;
 
/* function to check whether two strings are anagram of
each other */
bool areAnagram(string str1, string str2)
{
     //Get lengths of both strings
     int n1 = str1.length();
     int n2 = str2.length();
 
     //If length of both strings is not same, then they
     //cannot be anagram
     if (n1 != n2)
         return false ;
 
     //Sort both the strings
     sort(str1.begin(), str1.end());
     sort(str2.begin(), str2.end());
 
     //Compare sorted strings
     for ( int i = 0; i <n1; i++)
         if (str1[i] != str2[i])
             return false ;
 
     return true ;
}
 
//Driver code
int main()
{
     string str1 = "test" ;
     string str2 = "ttew" ;
 
     //Function Call
     if (areAnagram(str1, str2))
         cout <<"The two strings are anagram of each other" ;
     else
         cout <<"The two strings are not anagram of each "
                 "other" ;
 
     return 0;
}

Java

//JAVA program to check whether two strings
//are anagrams of each other
import java.io.*;
import java.util.Arrays;
import java.util.Collections;
 
class GFG {
 
     /* function to check whether two strings are
     anagram of each other */
     static boolean areAnagram( char [] str1, char [] str2)
     {
         //Get lenghts of both strings
         int n1 = str1.length;
         int n2 = str2.length;
 
         //If length of both strings is not same, //then they cannot be anagram
         if (n1 != n2)
             return false ;
 
         //Sort both strings
         Arrays.sort(str1);
         Arrays.sort(str2);
 
         //Compare sorted strings
         for ( int i = 0 ; i <n1; i++)
             if (str1[i] != str2[i])
                 return false ;
 
         return true ;
     }
 
     /* Driver Code*/
     public static void main(String args[])
     {
         char str1[] = { 't' , 'e' , 's' , 't' };
         char str2[] = { 't' , 't' , 'e' , 'w' };
       
         //Function Call
         if (areAnagram(str1, str2))
             System.out.println( "The two strings are"
                                + " anagram of each other" );
         else
             System.out.println( "The two strings are not"
                                + " anagram of each other" );
     }
}
 
//This code is contributed by Nikita Tiwari.

python

# Python program to check whether two strings are
# anagrams of each other
 
# function to check whether two strings are anagram
# of each other
 
 
def areAnagram(str1, str2):
     # Get lengths of both strings
     n1 = len (str1)
     n2 = len (str2)
 
     # If lenght of both strings is not same, then
     # they cannot be anagram
     if n1 ! = n2:
         return 0
 
     # Sort both strings
     str1 = sorted (str1)
     str2 = sorted (str2)
 
     # Compare sorted strings
     for i in range ( 0 , n1):
         if str1[i] ! = str2[i]:
             return 0
 
     return 1
 
 
# Driver code
str1 = "test"
str2 = "ttew"
 
# Function Call
if areAnagram(str1, str2):
     print ( "The two strings are anagram of each other" )
else :
     print ( "The two strings are not anagram of each other" )
 
# This code is contributed by Bhavya Jain

C#

//C# program to check whether two
//strings are anagrams of each other
using System;
using System.Collections;
class GFG {
 
     /* function to check whether two
strings are anagram of each other */
     public static bool areAnagram(ArrayList str1, ArrayList str2)
     {
         //Get lenghts of both strings
         int n1 = str1.Count;
         int n2 = str2.Count;
 
         //If length of both strings is not
         //same, then they cannot be anagram
         if (n1 != n2) {
             return false ;
         }
 
         //Sort both strings
         str1.Sort();
         str2.Sort();
 
         //Compare sorted strings
         for ( int i = 0; i <n1; i++) {
             if (str1[i] != str2[i]) {
                 return false ;
             }
         }
 
         return true ;
     }
 
     //Driver Code
     public static void Main( string [] args)
     {
         //create and initalize new ArrayList
         ArrayList str1 = new ArrayList();
         str1.Add( 't' );
         str1.Add( 'e' );
         str1.Add( 's' );
         str1.Add( 't' );
         //create and initalize new ArrayList
         ArrayList str2 = new ArrayList();
         str2.Add( 't' );
         str2.Add( 't' );
         str2.Add( 'e' );
         str2.Add( 'w' );
 
         //Function call
         if (areAnagram(str1, str2)) {
             Console.WriteLine( "The two strings are"
                               + " anagram of each other" );
         }
         else {
             Console.WriteLine( "The two strings are not"
                               + " anagram of each other" );
         }
     }
}
 
//This code is contributed by Shrikant13

输出如下：

The two strings are not anagram of each other

时间复杂度：O(nLogn)

方法2(计数字符)

此方法假定两个字符串中的可能字符集很小。在以下实现中, 假定使用8位存储字符, 并且可以有256个可能的字符。

  1. 为两个字符串创建大小为256的计数数组。将计数数组中的所有值初始化为0。
  2. 遍历两个字符串的每个字符, 并递增相应计数数组中的字符计数。
  3. 比较计数数组。如果两个计数数组相同, 则返回true。

以下是上述想法的实现：

C ++

//C++ program to check if two strings
//are anagrams of each other
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
 
/* function to check whether two strings are anagram of
each other */
bool areAnagram( char * str1, char * str2)
{
     //Create 2 count arrays and initialize all values as 0
     int count1[NO_OF_CHARS] = { 0 };
     int count2[NO_OF_CHARS] = { 0 };
     int i;
 
     //For each character in input strings, increment count
     //in the corresponding count array
     for (i = 0; str1[i] && str2[i]; i++) {
         count1[str1[i]]++;
         count2[str2[i]]++;
     }
 
     //If both strings are of different length. Removing
     //this condition will make the program fail for strings
     //like "aaca" and "aca"
     if (str1[i] || str2[i])
         return false ;
 
     //Compare count arrays
     for (i = 0; i <NO_OF_CHARS; i++)
         if (count1[i] != count2[i])
             return false ;
 
     return true ;
}
 
/* Driver code*/
int main()
{
     char str1[] = "lsbin" ;
     char str2[] = "forgeeksgeeks" ;
   
     //Function Call
     if (areAnagram(str1, str2))
         cout <<"The two strings are anagram of each other" ;
     else
         cout <<"The two strings are not anagram of each "
                 "other" ;
 
     return 0;
}
 
//This is code is contributed by rathbhupendra

C

//C program to check if two strings
//are anagrams of each other
#include <stdio.h>
#define NO_OF_CHARS 256
 
/* function to check whether two strings are anagram of
    each other */
bool areAnagram( char * str1, char * str2)
{
     //Create 2 count arrays and initialize all values as 0
     int count1[NO_OF_CHARS] = { 0 };
     int count2[NO_OF_CHARS] = { 0 };
     int i;
 
     //For each character in input strings, increment count
     //in the corresponding count array
     for (i = 0; str1[i] && str2[i]; i++) {
         count1[str1[i]]++;
         count2[str2[i]]++;
     }
 
     //If both strings are of different length. Removing
     //this condition will make the program fail for strings
     //like "aaca" and "aca"
     if (str1[i] || str2[i])
         return false ;
 
     //Compare count arrays
     for (i = 0; i <NO_OF_CHARS; i++)
         if (count1[i] != count2[i])
             return false ;
 
     return true ;
}
 
/* Driver code*/
int main()
{
     char str1[] = "lsbin" ;
     char str2[] = "forgeeksgeeks" ;
   
     //Function Call
     if (areAnagram(str1, str2))
         printf ( "The two strings are anagram of each other" );
     else
         printf ( "The two strings are not anagram of each "
                "other" );
 
     return 0;
}

Java

//JAVA program to check if two strings
//are anagrams of each other
import java.io.*;
import java.util.*;
 
class GFG {
 
     static int NO_OF_CHARS = 256 ;
 
     /* function to check whether two strings
     are anagram of each other */
     static boolean areAnagram( char str1[], char str2[])
     {
         //Create 2 count arrays and initialize
         //all values as 0
         int count1[] = new int [NO_OF_CHARS];
         Arrays.fill(count1, 0 );
         int count2[] = new int [NO_OF_CHARS];
         Arrays.fill(count2, 0 );
         int i;
 
         //For each character in input strings, //increment count in the corresponding
         //count array
         for (i = 0 ; i <str1.length && i <str2.length;
              i++) {
             count1[str1[i]]++;
             count2[str2[i]]++;
         }
 
         //If both strings are of different length.
         //Removing this condition will make the program
         //fail for strings like "aaca" and "aca"
         if (str1.length != str2.length)
             return false ;
 
         //Compare count arrays
         for (i = 0 ; i <NO_OF_CHARS; i++)
             if (count1[i] != count2[i])
                 return false ;
 
         return true ;
     }
 
     /* Driver code*/
     public static void main(String args[])
     {
         char str1[] = ( "lsbin" ).toCharArray();
         char str2[] = ( "forgeeksgeeks" ).toCharArray();
 
         //Function call
         if (areAnagram(str1, str2))
             System.out.println( "The two strings are"
                                + "anagram of each other" );
         else
             System.out.println( "The two strings are not"
                                + " anagram of each other" );
     }
}
 
//This code is contributed by Nikita Tiwari.

python

# Python program to check if two strings are anagrams of
# each other
NO_OF_CHARS = 256
 
# Function to check whether two strings are anagram of
# each other
 
 
def areAnagram(str1, str2):
 
     # Create two count arrays and initialize all values as 0
     count1 = [ 0 ] * NO_OF_CHARS
     count2 = [ 0 ] * NO_OF_CHARS
 
     # For each character in input strings, increment count
     # in the corresponding count array
     for i in str1:
         count1[ ord (i)] + = 1
 
     for i in str2:
         count2[ ord (i)] + = 1
 
     # If both strings are of different length. Removing this
     # condition will make the program fail for strings like
     # "aaca" and "aca"
     if len (str1) ! = len (str2):
         return 0
 
     # Compare count arrays
     for i in xrange (NO_OF_CHARS):
         if count1[i] ! = count2[i]:
             return 0
 
     return 1
 
 
# Driver code
str1 = "lsbin"
str2 = "forgeeksgeeks"
 
# Function call
if areAnagram(str1, str2):
     print "The two strings are anagram of each other"
else :
     print "The two strings are not anagram of each other"
 
# This code is contributed by Bhavya Jain

C#

//C# program to check if two strings
//are anagrams of each other
 
using System;
 
public class GFG {
 
     static int NO_OF_CHARS = 256;
 
     /* function to check whether two strings
     are anagram of each other */
     static bool areAnagram( char [] str1, char [] str2)
     {
         //Create 2 count arrays and initialize
         //all values as 0
         int [] count1 = new int [NO_OF_CHARS];
         int [] count2 = new int [NO_OF_CHARS];
         int i;
 
         //For each character in input strings, //increment count in the corresponding
         //count array
         for (i = 0; i <str1.Length && i <str2.Length;
              i++) {
             count1[str1[i]]++;
             count2[str2[i]]++;
         }
 
         //If both strings are of different length.
         //Removing this condition will make the program
         //fail for strings like "aaca" and "aca"
         if (str1.Length != str2.Length)
             return false ;
 
         //Compare count arrays
         for (i = 0; i <NO_OF_CHARS; i++)
             if (count1[i] != count2[i])
                 return false ;
 
         return true ;
     }
 
     /* Driver code*/
     public static void Main()
     {
         char [] str1 = ( "lsbin" ).ToCharArray();
         char [] str2 = ( "forgeeksgeeks" ).ToCharArray();
 
         //Function Call
         if (areAnagram(str1, str2))
             Console.WriteLine( "The two strings are"
                               + "anagram of each other" );
         else
             Console.WriteLine( "The two strings are not"
                               + " anagram of each other" );
     }
}
 
//This code contributed by 29AjayKumar

输出如下：

The two strings are anagram of each other

方法3(使用一个数组计数字符)

上述实现可以进一步是仅使用一个计数数组而不是两个。我们可以在count数组中为str1中的字符增加值, 并为str2中的字符减少。最后, 如果所有计数值均为0, 则两个字符串彼此相似。谢谢

高手

建议这种优化。

CPP

//C++ program to check if two strings
//are anagrams of each other
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
 
bool areAnagram( char * str1, char * str2)
{
     //Create a count array and initialize all values as 0
     int count[NO_OF_CHARS] = { 0 };
     int i;
 
     //For each character in input strings, increment count
     //in the corresponding count array
     for (i = 0; str1[i] && str2[i]; i++) {
         count[str1[i]]++;
         count[str2[i]]--;
     }
 
     //If both strings are of different length. Removing
     //this condition will make the program fail for strings
     //like "aaca" and "aca"
     if (str1[i] || str2[i])
         return false ;
 
     //See if there is any non-zero value in count array
     for (i = 0; i <NO_OF_CHARS; i++)
         if (count[i])
             return false ;
     return true ;
}
 
//Driver code
int main()
{
     char str1[] = "lsbin" ;
     char str2[] = "forgeeksgeeks" ;
   
     //Function call
     if (areAnagram(str1, str2))
         cout <<"The two strings are anagram of each other" ;
     else
         cout <<"The two strings are not anagram of each "
                 "other" ;
 
     return 0;
}

时间复杂度：O(n)

方法4(求和)

该问题可以在线性时间和恒定空间中完成。

  1. 我们将变量数count初始化为0。
  2. 然后, 我们取第一个字符串的所有字符的总和, 然后从第二个字符串减小所有字符的值。
  3. 如果Count值最终为0, 即在执行任何操作之前, 则为anagram, 否则为0。

下面是上述方法的实现：

C ++

//C++ program to check if two strings
//are anagrams of each other
#include <bits/stdc++.h>
using namespace std;
 
bool isAnagram(string c, string d)
{
     if (c.size() != d.size())
         return false ;
     int count = 0;
 
     //Take sum of all characters of first String
     for ( int i = 0; i <c.size(); i++) {
         count += c[i];
     }
 
     //Subtract the Value of all the characters of second
     //String
     for ( int i = 0; i <d.size(); i++) {
         count -= d[i];
     }
 
     //If Count = 0 then they are anagram
     //If count> 0 or count <0 then they are not anagram
     return (count == 0);
}
 
//Driver code
int main()
{
     char str1[] = "lsbin" ;
     char str2[] = "forgeeksgeeks" ;
   
     //Function call
     if (isAnagram(str1, str2))
         cout <<"The two strings are anagram of each other" ;
     else
         cout <<"The two strings are not anagram of each "
                 "other" ;
 
     return 0;
}

输出如下

The two strings are anagram of each other

时间复杂度：O(n)

辅助空间：O(1)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

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