我正在寻找一种方法来判断两个字符串是否是变位词。
Ex: string1 - abcde
string2 - abced
Ans = true
Ex: string1 - abcde
string2 - abcfed
Ans = false
我想到的解决方法是将两个字符串排序，然后比较两个字符串中的每个字符，直到其中一个字符串结束为止。这种方法的时间复杂度为O(logn)。我正在寻找其他更高效的方法，不会改变被比较的两个字符串。
寻找两个单词是否为相互颠倒字母构成的同字异序词。
27
- user514946
2
3可能是重复的问题：有没有一种简单的方法可以判断一个单词列表是否为同字母异序词？ - kennytm
请注意，对于具有O(1)（不依赖于字符集）堆栈内存使用的固定字符集，使用几个唯一排序是O(n)。当然，这仍然会修改两个字符串。 - Kaganar
23个回答
55
计算两个字符串中每个字符的频率。检查两个直方图是否匹配。O(n)时间，O(1)空间（假设是ASCII）（当然Unicode仍然是O(1)空间，但表格会变得非常大）。
- kennytm
10
17简单而有效。通过对一个字符串进行递增，对另一个字符串进行递减，并检查是否为0，可以轻松地将空间减半。对于Unicode字符，哈希映射表方法似乎比较合适。 - Eiko
8进行初始字符串长度检查可以帮助排除许多候选字符串。 - Srujan Kumar Gulla
2你好，你能否解释一下关于代码中的“计算频率”和“直方图”的更多细节？ - nyus2006
@kennytm 为什么空间复杂度是O(1)，而不是O(n)？ - aerin
1@ToussaintLouverture 因为只有95个ASCII字符。 - kennytm
显示剩余5条评论
33
获取质数表，足够用来将每个质数映射到每个字符。因此从1开始，通过该行，将数字乘以代表当前字符的质数。您将得到的数字仅取决于字符串中的字符，而不是它们的顺序，并且每个唯一的字符集都对应唯一的数字，因为任何数字只能被分解成一种方式。因此，您可以比较两个数字来判断字符串是否是相互排列的。
不幸的是，您必须使用多精度（任意精度）整数算术来执行此操作，否则当使用此方法时，您将遇到溢出或舍入异常。
您可以使用类似BigInteger、GMP、MPIR或IntX的库来实现。
伪代码:
prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101}
primehash(string)
Y = 1;
foreach character in string
Y = Y * prime[character-'a']
return Y
isanagram(str1, str2)
return primehash(str1)==primehash(str2)
- Vovanium
6
我认为这不会起作用。例如，2 + 5 = 7，所以如果a = 2，b = 3，c = 5和d = 7，如果一个字符串包含a和c，另一个字符串包含d，则在您的“总和”中会发生冲突。也许如果您首先检查每个字符串的长度是否相同，这种情况可能成立？ - runamok
3质数相乘，而不是相加。primehash("ac") = 2*5 = 10, primehash("d") = 7，因此它们不相等。由于数字与其质因数之间存在一对一的关系，所以不会发生碰撞。 - Vovanium
3可爱的 - 算术基本定理！https://zh.wikipedia.org/wiki/%E7%AE%97%E6%9C%AF%E5%9F%BA%E6%9C%AC%E5%AE%9A%E7%90%86 - StackG
很棒的算法，这对我帮助很大！ - Tudor
4唯一的问题是，你可能最终会得到一个非常大的整数，可能比系统的最大整数还要大。例如，primehash（“zzzzzzzzzz”）等于101的10次方，这比2的64次方还要大！ - viebel
1这个解决方案确实提供了时间复杂度为O(n)，而且不需要创建额外的数据结构，就像最受欢迎的解决方案所要求的那样。 - Francisco Carriedo Scher
24
- 创建一个哈希映射表，其中键为字母，值为该字母出现的次数。
- 对于第一个字符串，填充哈希映射表（O(n)）。
- 对于第二个字符串，从哈希映射表中减少计数并删除元素（O(n)）。
- 如果哈希映射表为空，则字符串是一组字母异位词，否则不是。
- Eternal Noob
5
不错的想法，在第一次运行时增加，在第二次运行时减少。然而，这里不需要哈希表，因为键值是预先知道的，可以用作数组索引。这将导致更快的实现。 - Philipp
3如果我们处理的是Unicode字符串，那么这可能是一个非常大的数组。 - user229044
1如果您通常比较小字符串，那么这不是很浪费吗？如果字符串平均较小（像大多数单词一样），那么只需将单词转换为字符数组，对数组进行排序，然后比较它们的相等性，可能比创建哈希映射、执行增量和减量，然后检查哈希映射是否为空的开销更小。 - Adam Parkin
1@AdamParkin 这只是在内存方面有些“浪费”。现在，内存非常便宜。对于大多数人来说，最重要的部分是运行时间。你的方法需要
O(n log n) 的时间进行排序，而提供的答案只需要 O(n)。此外，按照你所说的创建两个字符数组也需要 O(n) 的空间。 - ugo是的，就
O() 符号而言，我会同意它更有效率。但是，这忽略了常数因素，并且通常具有更好大 O 运行时间的算法在 n 很小的情况下性能较差。我想说的是，在这种情况下 n 可能很小，所以分配类似于 HashMap 这样昂贵的集合的开销可能比对小字符数组进行排序更昂贵。 - Adam Parkin8
步骤如下：
- 检查两个单词/字符串的长度是否相等，如果相等则继续检查是否为字谜，否则不执行任何操作
- 对两个单词/字符串进行排序，然后进行比较
JAVA代码如下:
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package anagram;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
/**
*
* @author Sunshine
*/
public class Anagram {
/**
* @param args the command line arguments
*/
public static void main(String[] args) throws IOException {
// TODO code application logic here
System.out.println("Enter the first string");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s1 = br.readLine().toLowerCase();
System.out.println("Enter the Second string");
BufferedReader br2 = new BufferedReader(new InputStreamReader(System.in));
String s2 = br2.readLine().toLowerCase();
char c1[] = null;
char c2[] = null;
if (s1.length() == s2.length()) {
c1 = s1.toCharArray();
c2 = s2.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
if (Arrays.equals(c1, c2)) {
System.out.println("Both strings are equal and hence they have anagram");
} else {
System.out.println("Sorry No anagram in the strings entred");
}
} else {
System.out.println("Sorry the string do not have anagram");
}
}
}
- fiddle
3
C#
public static bool AreAnagrams(string s1, string s2)
{
if (s1 == null) throw new ArgumentNullException("s1");
if (s2 == null) throw new ArgumentNullException("s2");
var chars = new Dictionary<char, int>();
foreach (char c in s1)
{
if (!chars.ContainsKey(c))
chars[c] = 0;
chars[c]++;
}
foreach (char c in s2)
{
if (!chars.ContainsKey(c))
return false;
chars[c]--;
}
return chars.Values.All(i => i == 0);
}
一些测试：
[TestMethod]
public void TestAnagrams()
{
Assert.IsTrue(StringUtil.AreAnagrams("anagramm", "nagaramm"));
Assert.IsTrue(StringUtil.AreAnagrams("anzagramm", "nagarzamm"));
Assert.IsTrue(StringUtil.AreAnagrams("anz121agramm", "nag12arz1amm"));
Assert.IsFalse(StringUtil.AreAnagrams("anagram", "nagaramm"));
Assert.IsFalse(StringUtil.AreAnagrams("nzagramm", "nagarzamm"));
Assert.IsFalse(StringUtil.AreAnagrams("anzagramm", "nag12arz1amm"));
}
- Ohad Schneider
2
让我们来看一个问题：给定两个字符串s和t，编写一个函数来确定t是否是s的字谜。
例如， s =“anagram”，t =“nagaram”，返回true。 s =“rat”，t =“car”，返回false。
方法1（使用HashMap）：
public class Method1 {
public static void main(String[] args) {
String a = "protijayi";
String b = "jayiproti";
System.out.println(isAnagram(a, b ));// output => true
}
private static boolean isAnagram(String a, String b) {
Map<Character ,Integer> map = new HashMap<>();
for( char c : a.toCharArray()) {
map.put(c, map.getOrDefault(c, 0 ) + 1 );
}
for(char c : b.toCharArray()) {
int count = map.getOrDefault(c, 0);
if(count == 0 ) {return false ; }
else {map.put(c, count - 1 ) ; }
}
return true;
}
}
方法二：
public class Method2 {
public static void main(String[] args) {
String a = "protijayi";
String b = "jayiproti";
System.out.println(isAnagram(a, b));// output=> true
}
private static boolean isAnagram(String a, String b) {
int[] alphabet = new int[26];
for(int i = 0 ; i < a.length() ;i++) {
alphabet[a.charAt(i) - 'a']++ ;
}
for (int i = 0; i < b.length(); i++) {
alphabet[b.charAt(i) - 'a']-- ;
}
for( int w : alphabet ) {
if(w != 0 ) {return false;}
}
return true;
}
}
方法三：
public class Method3 {
public static void main(String[] args) {
String a = "protijayi";
String b = "jayiproti";
System.out.println(isAnagram(a, b ));// output => true
}
private static boolean isAnagram(String a, String b) {
char[] ca = a.toCharArray() ;
char[] cb = b.toCharArray();
Arrays.sort( ca );
Arrays.sort( cb );
return Arrays.equals(ca , cb );
}
}
方法四：
public class AnagramsOrNot {
public static void main(String[] args) {
String a = "Protijayi";
String b = "jayiProti";
isAnagram(a, b);
}
private static void isAnagram(String a, String b) {
Map<Integer, Integer> map = new LinkedHashMap<>();
a.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) + 1));
System.out.println(map);
b.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) - 1));
System.out.println(map);
if (map.values().contains(0)) {
System.out.println("Anagrams");
} else {
System.out.println("Not Anagrams");
}
}
}
在Python中：
def areAnagram(a, b):
if len(a) != len(b): return False
count1 = [0] * 256
count2 = [0] * 256
for i in a:count1[ord(i)] += 1
for i in b:count2[ord(i)] += 1
for i in range(256):
if(count1[i] != count2[i]):return False
return True
str1 = "Giniiii"
str2 = "Protijayi"
print(areAnagram(str1, str2))
让我们来看另一个著名的面试问题：从给定字符串中分组异序词：
public class GroupAnagrams {
public static void main(String[] args) {
String a = "Gini Gina Protijayi iGin aGin jayiProti Soudipta";
Map<String, List<String>> map = Arrays.stream(a.split(" ")).collect(Collectors.groupingBy(GroupAnagrams::sortedString));
System.out.println("MAP => " + map);
map.forEach((k,v) -> System.out.println(k +" and the anagrams are =>" + v ));
/*
Look at the Map output:
MAP => {Giin=[Gini, iGin], Paiijorty=[Protijayi, jayiProti], Sadioptu=[Soudipta], Gain=[Gina, aGin]}
As we can see, there are multiple Lists. Hence, we have to use a flatMap(List::stream)
Now, Look at the output:
Paiijorty and the anagrams are =>[Protijayi, jayiProti]
Now, look at this output:
Sadioptu and the anagrams are =>[Soudipta]
List contains only word. No anagrams.
That means we have to work with map.values(). List contains all the anagrams.
*/
String stringFromMapHavingListofLists = map.values().stream().flatMap(List::stream).collect(Collectors.joining(" "));
System.out.println(stringFromMapHavingListofLists);
}
public static String sortedString(String a) {
String sortedString = a.chars().sorted()
.collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();
return sortedString;
}
/*
* The output : Gini iGin Protijayi jayiProti Soudipta Gina aGin
* All the anagrams are side by side.
*/
}
现在在Python中对字谜进行分组又变得容易了。我们需要按照以下步骤进行操作：先排序列表，然后创建一个字典。现在字典将告诉我们这些字谜的位置（字典的索引）。然后字典的值就是这些字谜的实际索引。请注意保留HTML标签。
def groupAnagrams(words):
# sort each word in the list
A = [''.join(sorted(word)) for word in words]
dict = {}
for indexofsamewords, names in enumerate(A):
dict.setdefault(names, []).append(indexofsamewords)
print(dict)
#{'AOOPR': [0, 2, 5, 11, 13], 'ABTU': [1, 3, 4], 'Sorry': [6], 'adnopr': [7], 'Sadioptu': [8, 16], ' KPaaehiklry': [9], 'Taeggllnouy': [10], 'Leov': [12], 'Paiijorty': [14, 18], 'Paaaikpr': [15], 'Saaaabhmryz': [17], ' CNaachlortttu': [19], 'Saaaaborvz': [20]}
for index in dict.values():
print([words[i] for i in index])
if __name__ == '__main__':
# list of words
words = ["ROOPA","TABU","OOPAR","BUTA","BUAT" , "PAROO","Soudipta",
"Kheyali Park", "Tollygaunge", "AROOP","Love","AOORP", "Protijayi","Paikpara","dipSouta","Shyambazaar",
"jayiProti", "North Calcutta", "Sovabazaar"]
groupAnagrams(words)
输出结果：
['ROOPA', 'OOPAR', 'PAROO', 'AROOP', 'AOORP']
['TABU', 'BUTA', 'BUAT']
['Soudipta', 'dipSouta']
['Kheyali Park']
['Tollygaunge']
['Love']
['Protijayi', 'jayiProti']
['Paikpara']
['Shyambazaar']
['North Calcutta']
['Sovabazaar']
另一个重要的变位词问题：找到出现最多次数的变位词。 在这个例子中，ROOPA是出现最多次数的单词。 因此，['ROOPA' 'OOPAR' 'PAROO' 'AROOP' 'AOORP']将成为最终输出。
from sqlite3 import collections
from statistics import mode, mean
import numpy as np
# list of words
words = ["ROOPA","TABU","OOPAR","BUTA","BUAT" , "PAROO","Soudipta",
"Kheyali Park", "Tollygaunge", "AROOP","Love","AOORP",
"Protijayi","Paikpara","dipSouta","Shyambazaar",
"jayiProti", "North Calcutta", "Sovabazaar"]
print(".....Method 1....... ")
sortedwords = [''.join(sorted(word)) for word in words]
print(sortedwords)
print("...........")
LongestAnagram = np.array(words)[np.array(sortedwords) == mode(sortedwords)]
# Longest anagram
print("Longest anagram by Method 1:")
print(LongestAnagram)
print(".....................................................")
print(".....Method 2....... ")
A = [''.join(sorted(word)) for word in words]
dict = {}
for indexofsamewords,samewords in enumerate(A):
dict.setdefault(samewords,[]).append(samewords)
#print(dict)
#{'AOOPR': ['AOOPR', 'AOOPR', 'AOOPR', 'AOOPR', 'AOOPR'], 'ABTU': ['ABTU', 'ABTU', 'ABTU'], 'Sadioptu': ['Sadioptu', 'Sadioptu'], ' KPaaehiklry': [' KPaaehiklry'], 'Taeggllnouy': ['Taeggllnouy'], 'Leov': ['Leov'], 'Paiijorty': ['Paiijorty', 'Paiijorty'], 'Paaaikpr': ['Paaaikpr'], 'Saaaabhmryz': ['Saaaabhmryz'], ' CNaachlortttu': [' CNaachlortttu'], 'Saaaaborvz': ['Saaaaborvz']}
aa = max(dict.items() , key = lambda x : len(x[1]))
print("aa => " , aa)
word, anagrams = aa
print("Longest anagram by Method 2:")
print(" ".join(anagrams))
输出：
.....Method 1.......
['AOOPR', 'ABTU', 'AOOPR', 'ABTU', 'ABTU', 'AOOPR', 'Sadioptu', ' KPaaehiklry', 'Taeggllnouy', 'AOOPR', 'Leov', 'AOOPR', 'Paiijorty', 'Paaaikpr', 'Sadioptu', 'Saaaabhmryz', 'Paiijorty', ' CNaachlortttu', 'Saaaaborvz']
...........
Longest anagram by Method 1:
['ROOPA' 'OOPAR' 'PAROO' 'AROOP' 'AOORP']
.....................................................
.....Method 2.......
aa => ('AOOPR', ['AOOPR', 'AOOPR', 'AOOPR', 'AOOPR', 'AOOPR'])
Longest anagram by Method 2:
AOOPR AOOPR AOOPR AOOPR AOOPR
- Soudipta Dutta
2
查找两个单词是否是变位词的代码:
逻辑已经在几个答案中解释过了，有些人要求代码。这个解决方案可以在O(n)时间内产生结果。
这种方法计算每个字符出现的次数，并将其存储在每个字符串的相应ASCII位置中。然后比较两个数组的计数。如果不相等，则给定的字符串不是变位词。
public boolean isAnagram(String str1, String str2)
{
//To get the no of occurrences of each character and store it in their ASCII location
int[] strCountArr1=getASCIICountArr(str1);
int[] strCountArr2=getASCIICountArr(str2);
//To Test whether the two arrays have the same count of characters. Array size 256 since ASCII 256 unique values
for(int i=0;i<256;i++)
{
if(strCountArr1[i]!=strCountArr2[i])
return false;
}
return true;
}
public int[] getASCIICountArr(String str)
{
char c;
//Array size 256 for ASCII
int[] strCountArr=new int[256];
for(int i=0;i<str.length();i++)
{
c=str.charAt(i);
c=Character.toUpperCase(c);// If both the cases are considered to be the same
strCountArr[(int)c]++; //To increment the count in the character's ASCII location
}
return strCountArr;
}
- Dany
3
哦！！！在这种特定情况下，“直方图”就是这个意思。谢谢你。但是有一个问题，这个解决方案的空间复杂度是O(N)，为什么顶部评论说它是O(1)？ - nyus2006
@S.H.-所有字符串的数组大小均为256。如果您在一个字符串中输入一百万个字符，它仍将储存在一个大小为256的数组中，这是一个常数。因此，其空间复杂度为O(1)。 - Dany
是的，你是正确的，O(256)渐进地等同于O(1)。谢谢！ - nyus2006
2
使用允许每个字符O(1)查找的ASCII哈希映射。
上面列出的Java示例正在转换为似乎不完整的小写。我有一个C语言示例，它仅初始化了一个哈希映射数组 ASCII值为“ -1”。
如果string2与string1的长度不同，则不是变位词。
否则，我们将适当的哈希映射值更新为0，以表示string1和string2中的每个字符。
然后对于string1中的每个字符，我们更新哈希映射中的计数。类似地，我们减少string2中每个字符的计数值。
如果它们是变位词，则结果应该将每个字符设置为0。否则，由string1设置的一些正值保留。
上面列出的Java示例正在转换为似乎不完整的小写。我有一个C语言示例，它仅初始化了一个哈希映射数组 ASCII值为“ -1”。
如果string2与string1的长度不同，则不是变位词。
否则，我们将适当的哈希映射值更新为0，以表示string1和string2中的每个字符。
然后对于string1中的每个字符，我们更新哈希映射中的计数。类似地，我们减少string2中每个字符的计数值。
如果它们是变位词，则结果应该将每个字符设置为0。否则，由string1设置的一些正值保留。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ARRAYMAX 128
#define True 1
#define False 0
int isAnagram(const char *string1,
const char *string2) {
int str1len = strlen(string1);
int str2len = strlen(string2);
if (str1len != str2len) /* Simple string length test */
return False;
int * ascii_hashtbl = (int * ) malloc((sizeof(int) * ARRAYMAX));
if (ascii_hashtbl == NULL) {
fprintf(stderr, "Memory allocation failed\n");
return -1;
}
memset((void *)ascii_hashtbl, -1, sizeof(int) * ARRAYMAX);
int index = 0;
while (index < str1len) { /* Populate hash_table for each ASCII value
in string1*/
ascii_hashtbl[(int)string1[index]] = 0;
ascii_hashtbl[(int)string2[index]] = 0;
index++;
}
index = index - 1;
while (index >= 0) {
ascii_hashtbl[(int)string1[index]]++; /* Increment something */
ascii_hashtbl[(int)string2[index]]--; /* Decrement something */
index--;
}
/* Use hash_table to compare string2 */
index = 0;
while (index < str1len) {
if (ascii_hashtbl[(int)string1[index]] != 0) {
/* some char is missing in string2 from string1 */
free(ascii_hashtbl);
ascii_hashtbl = NULL;
return False;
}
index++;
}
free(ascii_hashtbl);
ascii_hashtbl = NULL;
return True;
}
int main () {
char array1[ARRAYMAX], array2[ARRAYMAX];
int flag;
printf("Enter the string\n");
fgets(array1, ARRAYMAX, stdin);
printf("Enter another string\n");
fgets(array2, ARRAYMAX, stdin);
array1[strcspn(array1, "\r\n")] = 0;
array2[strcspn(array2, "\r\n")] = 0;
flag = isAnagram(array1, array2);
if (flag == 1)
printf("%s and %s are anagrams.\n", array1, array2);
else if (flag == 0)
printf("%s and %s are not anagrams.\n", array1, array2);
return 0;
}
- Rock
1
这样可以吗？
a = "lai d" b = "di al" sorteda = [] sortedb = []
for i in a: if i != " ": sorteda.append(i)
c = len(b) for i in range(c): for x in b: if x != " ": sortedb.append(x) c -= 1 break
sorteda.sort(key=str.lower) sortedb.sort(key=str.lower) print(sortedb) print(sorteda) print(sortedb == sorteda)
- AAF
2
您在字符串中的选择可能会赚取足够的攻击标志，以致于您的答案被删除。请考虑进行修订。然而，我理解它们为什么对您的示例很方便。 - Tim Post
好的，我只是为了好玩改变了我的字谜，绝不是有意冒犯！ - AAF
1
你可以通过先检查长度，然后对数字进行快速校验（不要使用复杂的算法，因为这可能比排序更糟糕，只需对序数值进行求和），然后进行排序，最后进行比较，从而显著改善最佳情况和平均情况。
如果字符串非常短，则在许多语言中，校验和开销与排序开销相差不大。
- Orbling
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接