检查两个字符串是否是彼此的排列

Question

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

Answer 1

• 对两个字符串的字符进行排序.
• 比较结果,看看它们是否相同.

编辑:

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

我没有一种有效的方法来递归地做到这一点.一种低效的方式(O(n ^ 2),如果直接实施则更糟)是这样的:

• 如果两个字符串都由一个相同的字符组成,则返回true
• 除此以外:
  • 从第一个字符串中删除一个字符
  • 查看第二个字符串是否出现此字符
  • 如果不存在,则返回false
  • 否则,删除所述字符并递归地将算法应用于两个字符串的余数.

Answer 2

把@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);
}

Answer 3

创建一个Hashmap,其中第一个字符串的字符为键,出现次数为value; 然后遍历第二个字符串,对于每个字符,查找哈希表并减少数字,如果它大于零.如果找不到条目或条目已经为0,则字符串不是彼此的排列.显然,字符串必须具有相同的长度.

Answer 4

HashMap中的线性时间解决方案.遍历并在HashMap中放置第一个String,保留每个字符的计数.遍历第二个String,如果它已经在hashmap中,则将计数减少1.最后,如果所有字符都在字符串中,则hashmap中的值对于每个字符将为0.

public class StringPermutationofEachOther {
    public static void main(String[] args)
    {

    String s1= "abc";
    String s2 ="bbb";
    System.out.println(perm(s1,s2));
}
    public static boolean perm(String s1, String s2)
    { HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    int count =1;
        if(s1.length()!=s2.length())
        {
            return false;
        }
            for(Character c: s1.toCharArray())
            {
                if(!map.containsKey(c))
                    map.put(c, count);

                else
                    map.put(c, count+1);

            }
            for(Character c: s2.toCharArray())
            {
                if(!map.containsKey(c))
                    return false;

                else
                    map.put(c, count-1);
            }
            for(Character c: map.keySet())
            {
                if(map.get(c)!=0)
                    return false;
            }
        return true;
    }


}

Answer 5

您可以尝试使用 XOR，如果一个字符串是另一个字符串的渗透，则它们应该具有基本相同的字符。唯一的区别只是字符的顺序。因此，使用 XOR 技巧可以帮助您摆脱顺序并只关注字符。

public static boolean isPermutation(String s1, String s2){
    if (s1.length() != s2.length()) return false;
    int checker = 0;
    for(int i = 0; i < s1.length();i++ ){
        checker ^= s1.charAt(i) ^ s2.charAt(i);
    }

    return checker == 0;
}