检查两个字符串是否是彼此的排列 [英] Checking if two strings are permutations of each other

问题描述

如何确定两个字符串是否是彼此的排列

How to determine if two strings are permutations of each other

推荐答案

• 对两个字符串进行排序字符。


• 比较结果，看它们是否相同。



编辑：

上述方法相当有效--O（n * log（n）），正如其他人所示，非常容易实现标准Java API。更有效（但也更多的工作）将计算和比较每个字符的出现次数，使用char值作为计数数组的索引。

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 ^ 2），如果直接实施则更糟）是：

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:



• 如果两个字符串都包含一个相同的字符，返回true


• 否则：
  
  
  
  
  • 从第一个字符串中删除一个字符
  
  
  • 查看第二个字符串是否出现此字符
  
  
  • 如果不存在，则返回false
  
  
  • 否则，删除所述字符并递归地将算法应用于余数两个字符串。
  
  
  • 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.

    这篇关于检查两个字符串是否是彼此的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！