原文:
给定一个字符串数组，查找给定数组中的所有字谜对。 例:
input: arr[] = {"geeksquiz", "geeksforgeeks", "abcd",
"forgeeksgeeks", "zuiqkeegs"};
output: (geeksforgeeks, forgeeksgeeks), (geeksquiz, zuiqkeegs)
我们可以通过计数数组内找到两个字符串是否为字谜(见本
c
#include
using namespace std;
#define no_of_chars 256
/* function to check whether two strings are anagram of each other */
bool areanagram(string str1, string str2)
{
// create two count arrays 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;
}
// this function prints all anagram pairs in a given array of strings
void findallanagrams(string arr[], int n)
{
for (int i = 0; i < n; i )
for (int j = i 1; j < n; j )
if (areanagram(arr[i], arr[j]))
cout << arr[i] << " is anagram of " << arr[j] << endl;
}
/* driver program to test to print printdups*/
int main()
{
string arr[] = {"geeksquiz", "geeksforgeeks", "abcd",
"forgeeksgeeks", "zuiqkeegs"};
int n = sizeof(arr)/sizeof(arr[0]);
findallanagrams(arr, n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print all pairs of
// anagrams in a given array of strings
public class gfg
{
static final int no_of_chars = 256;
/* function to check whether two
strings are anagram of each other */
static boolean areanagram(string str1, string str2)
{
// create two count arrays and initialize
// all values as 0
int[] count = 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 )
{
count[str1.charat(i)] ;
count[str2.charat(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;
// see if there is any non-zero value in
// count array
for (i = 0; i < no_of_chars; i )
if (count[i] != 0)
return false;
return true;
}
// this function prints all anagram pairs in a
// given array of strings
static void findallanagrams(string arr[], int n)
{
for (int i = 0; i < n; i )
for (int j = i 1; j < n; j )
if (areanagram(arr[i], arr[j]))
system.out.println(arr[i]
" is anagram of " arr[j]);
}
/* driver program to test to print printdups*/
public static void main(string args[])
{
string arr[] = {"geeksquiz", "geeksforgeeks",
"abcd", "forgeeksgeeks",
"zuiqkeegs"};
int n = arr.length;
findallanagrams(arr, n);
}
}
// this code is contributed by sumit ghosh
python 3
# python3 program to find
# best meeting point in 2d array
no_of_chars = 256
# function to check whether two strings
# are anagram of each other
def areanagram(str1: str, str2: str) -> bool:
# create two count arrays and
# initialize all values as 0
count = [0] * no_of_chars
i = 0
# for each character in input strings,
# increment count in the corresponding
# count array
while i < len(str1) and i < len(str2):
count[ord(str1[i])] = 1
count[ord(str2[i])] -= 1
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 false
# see if there is any non-zero value
# in count array
for i in range(no_of_chars):
if count[i]:
return false
return true
# this function prints all anagram pairs
# in a given array of strings
def findallanagrams(arr: list, n: int):
for i in range(n):
for j in range(i 1, n):
if areanagram(arr[i], arr[j]):
print(arr[i], "is anagram of", arr[j])
# driver code
if __name__ == "__main__":
arr = ["geeksquiz", "geeksforgeeks",
"abcd", "forgeeksgeeks", "zuiqkeegs"]
n = len(arr)
findallanagrams(arr, n)
# this code is contributed by
# sanjeev2552
c
// c# program to print all pairs of
// anagrams in a given array of strings
using system;
class gfg
{
static int no_of_chars = 256;
/* function to check whether two
strings are anagram of each other */
static bool areanagram(string str1, string str2)
{
// create two count arrays and initialize
// all values as 0
int[] count = 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 )
{
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.length != str2.length)
return false;
// see if there is any non-zero value in
// count array
for (i = 0; i < no_of_chars; i )
if (count[i] != 0)
return false;
return true;
}
// this function prints all anagram pairs in a
// given array of strings
static void findallanagrams(string []arr, int n)
{
for (int i = 0; i < n; i )
for (int j = i 1; j < n; j )
if (areanagram(arr[i], arr[j]))
console.writeline(arr[i]
" is anagram of " arr[j]);
}
/* driver program to test to print printdups*/
public static void main()
{
string []arr = {"geeksquiz", "geeksforgeeks",
"abcd", "forgeeksgeeks",
"zuiqkeegs"};
int n = arr.length;
findallanagrams(arr, n);
}
}
// this code is contributed by nitin mittal
java 描述语言
输出:
geeksquiz is anagram of zuiqkeegs
geeksforgeeks is anagram of forgeeksgeeks
上述解的时间复杂度为 o(n 2 m)，其中 n 为字符串个数，m 为字符串最大长度。 优化: 我们可以使用以下方法优化上述pg电子试玩链接的解决方案。 1) 使用排序:我们可以对字符串数组进行排序，这样所有的字谜就都在一起了。然后通过线性遍历排序后的数组来打印所有的字谜。这个pg电子试玩链接的解决方案的时间复杂度是 o(mnlogn)(我们将在排序中进行 o(nlogn)比较，并且比较将花费 o(m)时间) 2) 使用哈希:*我们可以为一个字符串构建一个哈希函数，如异或或所有字符的 ascii 值之和。使用这样的哈希函数，我们可以构建一个哈希表。在构建哈希表时，我们可以检查一个值是否已经被哈希。如果是，我们可以调用 areanagrams()来检查两个字符串是否实际上是字谜(注意异或或 ascii 值的和是不够的，参见 kaushik lele 的评论 ) 本文由 abhishek 供稿。如果您发现任何不正确的地方或想分享更多关于上述主题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
