Java 检查两个字符串是否是彼此的排列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2131997/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Checking if two strings are permutations of each other
提问by
How to determine if two strings are permutations of each other
如何确定两个字符串是否是彼此的排列
回答by Michael Borgwardt
- Sort the two strings's characters.
- Compare the results to see if they're identical.
- 对两个字符串的字符进行排序。
- 比较结果以查看它们是否相同。
Edit:
编辑：
The above method is reasonably efficient - O(n*log(n)) and, as others have shown, very easy to implement using the standard Java API. Even more efficient (but also more work) would be counting and comparing the occurrence of each character, using the char value as index into an array of counts.
上述方法相当有效 - O(n*log(n)) 并且，正如其他人所展示的，使用标准 Java API 非常容易实现。使用 char 值作为计数数组的索引，计算和比较每个字符的出现次数会更有效（但也需要做更多工作）。
I do not thing there is an efficient way to do it recursively. An inefficient way (O(n^2), worse if implemented straightforwardly) is this:
我不认为有一种有效的方法可以递归地做到这一点。一种低效的方式（O(n^2)，如果直接实现更糟）是这样的：
- If both strings consist of one identical character, return true
- Otherwise:
- remove one character from the first string
- Look through second string for occurrence of this character
- If not present, return false
- Otherwise, remove said character and apply algorithm recursively to the remainders of both strings.
- 如果两个字符串都包含一个相同的字符，则返回 true
- 除此以外：
- 从第一个字符串中删除一个字符
- 查看第二个字符串是否出现此字符
- 如果不存在，返回false
- 否则，删除所述字符并将算法递归应用于两个字符串的其余部分。
回答by Amarghosh
To put @Michael Borgwardt's words in to code:
将@Michael Borgwardt 的话放入代码中：
public boolean checkAnagram(String str1, String str2) {
if (str1.length() != str2.length())
return false;
char[] a = str1.toCharArray();
char[] b = str2.toCharArray();
Arrays.sort(a);
Arrays.sort(b);
return Arrays.equals(a, b);
}
回答by kennytm
- Sort the 2 strings by characters and compare if they're the same (O(n log n) time, O(n) space), or
- Tally the character frequency of the 2 strings and compare if they're the same (O(n) time, O(n) space).
- 按字符对 2 个字符串进行排序并比较它们是否相同（O(n log n) 时间，O(n) 空间），或
- 计算 2 个字符串的字符频率并比较它们是否相同（O(n) 时间，O(n) 空间）。
回答by Erich Kitzmueller
Create a Hashmap with the characters of the first string as keys and the number of occurances as value; then go through the second string and for each character, look up the hash table and decrement the number if it is greater than zero. If you don't find an entry or if it is already 0, the strings are not a permutation of each other. Obviously, the string must have the same length.
创建一个以第一个字符串的字符为键，出现次数为值的Hashmap；然后遍历第二个字符串，对于每个字符，查找哈希表，如果它大于零，则递减该数字。如果您没有找到一个条目或者它已经是 0，则这些字符串不是彼此的排列。显然，字符串必须具有相同的长度。
回答by JRL
You might take a look at String.toCharArrayand Arrays.sort
回答by fastcodejava
First you check the lengths (n), if they are not same, they cannot be permutations of each other. Now create two HashMap<Character, Integer>. Iterate over each string and put the number of times each character occur in the string. E.g. if the string is aaaaa, the map will have just one element with key a and value 5. Now check if the two maps are identical. This is an O(n)algorithm.
首先检查长度 ( n)，如果它们不相同，则它们不能相互排列。现在创建两个HashMap<Character, Integer>. 迭代每个字符串并把每个字符出现在字符串中的次数。例如，如果字符串是 aaaaa，则映射将只有一个键为 a 且值为 5 的元素。现在检查两个映射是否相同。这是一个O(n)算法。
EDIT with code snippet :
编辑代码片段：
boolean checkPermutation(String str1, String str2) {
char[] chars1 = str1.toCharArray();
char[] chars2 = str2.toCharArray();
Map<Character, Integer> map1 = new HashMap<Character, Integer>();
Map<Character, Integer> map2 = new HashMap<Character, Integer>();
for (char c : chars1) {
int occ = 1;
if (map1.containsKey(c) {
occ = map1.get(c);
occ++;
}
map1.put(c, occ);
}
// now do the same for chars2 and map2
if (map1.size() != map2.size()) {
return false;
}
for (char c : map1.keySet()) {
if (!map2.containsKey(c) || map1.get(c) != map2.get(c)) {
return false;
}
}
return true;
}
回答by dfa
I'm working on a Java library that should simplify your task. You can re-implement this algorithmusing only two method calls:
我正在开发一个可以简化您的任务的 Java 库。您只需使用两个方法调用即可重新实现此算法：
boolean arePermutationsOfSameString(String s1, String s2) {
s1 = $(s1).sort().join();
s2 = $(s2).sort().join();
return s1.equals(s2);
}
testcase
测试用例
@Test
public void stringPermutationCheck() {
// true cases
assertThat(arePermutationsOfSameString("abc", "acb"), is(true));
assertThat(arePermutationsOfSameString("bac", "bca"), is(true));
assertThat(arePermutationsOfSameString("cab", "cba"), is(true));
// false cases
assertThat(arePermutationsOfSameString("cab", "acba"), is(false));
assertThat(arePermutationsOfSameString("cab", "acbb"), is(false));
// corner cases
assertThat(arePermutationsOfSameString("", ""), is(true));
assertThat(arePermutationsOfSameString("", null), is(true));
assertThat(arePermutationsOfSameString(null, ""), is(true));
assertThat(arePermutationsOfSameString(null, null), is(true));
}
PS
聚苯乙烯
In the case you can clone the souces at bitbucket.
在这种情况下，您可以在 bitbucket克隆源。
回答by finnw
The obligatory Guavaone-liner:
强制性番石榴单线：
boolean isAnagram(String s1, String s2) {
return ImmutableMultiset.copyOf(Chars.asList(s1.toCharArray())).equals(ImmutableMultiset.copyOf(Chars.asList(s2.toCharArray())));
}
(Just for fun. I don't recommend submitting this for your assignment.)
（只是为了好玩。我不建议您将此提交给您的作业。）
回答by finnw
As you requested, here's a complete solution using recursion. Now all you have to do is:
根据您的要求，这是使用递归的完整解决方案。现在你所要做的就是：
- Figure out what language this is
- Translate it to Java.
- 弄清楚这是什么语言
- 将其翻译成 Java。
Good luck :-)
祝你好运 ：-）
proc isAnagram(s1, s2);
return {s1, s2} = {''} or
(s2 /= '' and
(exists c = s1(i) |
s2(1) = c and
isAnagram(s1(1..i-1) + s1(i+1..), s2(2..))));
end isAnagram;
回答by lateralpunk
I did this in C if anyone cares. It assumes ASCII values and uses the characters ordinal value:
如果有人关心的话，我用 C 做了这个。它假定 ASCII 值并使用字符序数值：
bool is_permutation(const char *a, const char *b)
{
if (a == NULL || b == NULL)
return false;
if (strlen(a) != strlen(b))
return false;
int sum_a = 0, sum_b = 0;
while (*a != '##代码##')
sum_a += (int)*a++;
while (*b != '##代码##')
sum_b += (int)*b++;
return (sum_a == sum_b);
}
