如何检查两个字符串是否是“兄弟字符串”？

问题描述：

如果字符串A和字符串B包含相同的字符，则称它们为“兄弟字符串”。
例如：“abc”和“cab”，“aabb”和“baab”。
问题是如何检查两个字符串是兄弟字符串（快）？如何检查两个字符串是否是“兄弟字符串”？

你有一个字母表，所以可编码字符的数量是已知的和有限的。桶对字符串进行排序并在'O（n）'中进行比较。 – davin

关于最简单的你可以做到这一点：'sorted（a）== sorted（b）'（Python） –

这是一个简单的案例http://stackoverflow.com/q/6691184/395626 – ruslik

答

排序，然后比较他们，或使每个字符的数量在地图上某种然后比较最后的计数。

那么它是哪一个呢？排序还是计数？这两种选择有什么区别？ – svick

计数是O（n），排序取决于您使用的方法。 – lostyzd

计数很简单...制作两个26-整数数组，遍历字符串并为字符串中的每个字符递增相应的计数器。最后，如果我理解他描述的是正确的，那么你将XOR计数器放在一起，如果一切都为0，那么它们就是兄弟。 – bdares

答

什么都字符数组，并以计数的B的等” 的数量比比较两个数组的

答

这种情况下最快的算法具有O（n）的复杂度，其中n是最长字符串的长度。

In fact in O（n）you can create a array（one for each string）where characters are stored。此外，你需要另外的O（n）时间来做测试。

如果我理解他描述的是正确的，那么这些字符串必须具有相同的长度。 –

我不知道你在说什么。 – svick

@AurelioDeRosa，我知道什么是O符号。但我不知道你的答案如何与问题实际相关。你谈论创建一些数组，然后做一些测试。但是你不清楚你想要创建什么样的阵列以及你想要执行什么样的测试。 – svick

答

只需计算每个字符在字符串中出现的次数。然后他们比较两个字符串的计数。

如果字符串总是ASCII或一些8位编码，那么简单数组就足够了。

如果它们可以包含Unicode字符，请使用哈希映射。

对downvoter：谨慎评论你认为这个答案错了吗？ – svick

答

让我来展示我的变体。每个字符都有它的int ASCII值。所以我认为，你可以将两个字符串的所有字符相乘，并比较两个产品。例如：

private static boolean compareForBrother(String s1, String s2) { 
    long lProduct= 1L; 
    for (byte b : s1.getBytes()) { 
     lProduct *= b; 
    } 

    long lProduct2= 1L; 
    for (byte b : s2.getBytes()) { 
     lProduct2 *= b; 
    } 

    return (lProduct2 == lProduct); 
}

答

比较每个字符串中的字符集。

在Python中，是这样的：

if set(stringA) == set(stringB): 
    print("%s and %s are brother strings" % (stringA, stringB))

答

如何检查两个字符串是否是“兄弟字符串”？

相关推荐