PHP-比较字符串相似

Question

求算法 比较 abcdef,badcfe 这两个字符串中的字母以及个数是否完全一致

当前我能想到的就是

既然 每个 都是乱的 那么我们按一个专门的规则 也就是自然排序 经过排序之后 他们肯定是按字母从大到小去排列的

但是肯定有更好的方案,求高手分享

Answer 1

如果仅是a-z, 用数组array[26] 做 字母 到 个数的映射.

遍历字符串得到两个结果数组, 比较两个数组是否相等.

Answer 2

不能使用额外空间的话就需要quicksort一下，时间复杂度O(nlogn).
可以使用额外空间的话就hashmap记录字符和出现次处，时间复杂度O(n).

bool func(const string &a, const string &b)
{
if (a.size() != b.size()) return false;
unordered_map<char, int> mapping;
for (int i = 0; i < a.size(); i++)
{
if (mapping.findkey(a[i]) == mapping.end())
mapping[a[i]] = 1;
else
mapping[a[i]]++;
if (mapping.findkey(b[i]) == mapping.end())
mapping[b[i]] = -1;
else
mapping[b[i]]--;
}
for (auto it = mapping.begin(); it != mapping.end(); it++)
{
if (it->second != 0) return false;
}
return true;
}