找出2个相似或不相似的字符串

规则：2个字符串，a和b，它们都由ASCII字符和非ASCII字符组成（例如，中文字符gbk编码）。

If the non-ASCII chars contained in b also show up in a and no less than the times they appear in b, then we say b is similar with a. 

例如：

 a = "ab中ef日jkl中本" //non-ASCII chars:'中'(twice), '日'(once), '本'(once) b = "bej中中日" //non-ASCII chars:'中'(twice), '日'(once) c = 'lk日日日' //non-ASCII chars:'日'(3 times, more than twice in a) 

根据规则，b与a类似，但c不是。 这是我的问题：我们不知道a和b中有多少非ASCII字符，可能很多。 因此，为了找出a和b中出现非ASCII字符的次数，我应该使用哈希表来存储它们的出现时间吗？ 以字符串a为例：

 [non-ASCII's hash-value]:[times]中's hash-val : 2日's hash-val : 1本's hash-val : 1 

检查字符串b，如果我们在b中遇到非ASCII字符，然后哈希它并检查一个哈希表，如果字符串存在于哈希表中，那么它的出现次数会减少1.如果出现次数小于0（-1），那么我们说b与a不相似。

或者有更好的方法吗？

PS：我逐字节读取字符串，如果字节小于128，那么我将其作为ASCII字符，否则我将其作为非ASCII字符（多字节）的一部分。 我正在做的是找出非ASCII字符。 这样对吗？

Answer 1

你问过两个问题：

1. 我们可以使用哈希表来计算非ASCII字符吗？ 答：当然。 在读取字符（ 而不是字节 ）时，请检查代码点。 对于任何大于127的代码点，将其放入计数哈希表中。 对于字符c，如果c不在表中，则添加（c，1），如果c已经在表中，则将（c，x）更新为（c，x + 1）。

2. 有没有更好的方法来解决这个问题，而不是在你运行b时递增计数和递减计数的方法？ 如果您的哈希表实现提供了几乎O（1）访问，那么我怀疑不是。 您正在查看字符串中的每个字符一次，并且对于每个字符，您正在执行哈希表插入或查找以及加法或减法，并检查0。对于未排序的字符串，您必须查看所有字符无论如何，这两个字符串，所以你认为，你已经给出了最好的解决方案。

面试官可能正在寻找你说的话，“嗯，如果这些字符串实际上是无法记忆的大量文件，我该怎么办？” 或者你问“好的字符串是否排序？因为如果它们是，我可以更快地做到……”。

但现在让我们说这些字符串很大。 您在内存中存储的唯一内容是哈希表。 Unicode只有大约100万个代码点，并且你为每个代码点存储一个整数计数，所以即使你从千兆字节大小的文件中获取数据，你的哈希表只需要大约4MB左右（或者是这个的一小部分，因为它会在头顶上）。

在没有任何其他条件的情况下，您的算法很好。 事先对字符串进行排序并不好; 它占用更多内存，而不是线性时间操作。

附录

由于你的原始注释提到了char类型而不是wchar_t ，我想我会展示一个使用宽字符串的例子。 见http://codepad.org/B3MXOgqc

希望有所帮助。

附录2

好的，这是一个C程序，它显示了如何通过宽字符串并在角色级别工作：

http://codepad.org/QVX3QPat

这是一个非常短的程序，所以我也将它贴在这里：

 #include  #include  #include  char *s1 = "abd中日"; wchar_t *s2 = L"abd中日"; int main() { int i, n; printf("length of s1 is %d\n", strlen(s1)); printf("length of s2 using wcslen is %d\n", wcslen(s2)); printf("The codepoints of the characters of s2 are\n"); for (i = 0, n = wcslen(s2); i < n; i++) { printf("%02x\n", s2[i]); } return 0; } 

输出：

 length of s1 is 9 length of s2 using wcslen is 5 The codepoints of the characters of s2 are 61 62 64 4e2d 65e5 

我们可以从中学到什么？ 几件事：

1. 如果对CJK字符使用普通旧char ，那么字符串长度将是错误的 。
2. 要在C中使用Unicode字符，请使用wchar_t
3. 字符串文字对于宽字符串具有前导L

在这个例子中，我定义了一个带有CJK字符的字符串，并使用了wchar_t和一个带有wcslen的for循环。 请注意，我正在使用真实字符，而不是BYTES，所以我得到了正确的字符数，即5.现在我打印出每个代码点。 在你的面试问题中，你将看到代码点是否>= 128.我用Hex显示它们，就像文化一样，所以你可以寻找> 0x7F。 🙂

附录3

http://tldp.org/HOWTO/Unicode-HOWTO-6.html中的一些注释值得一读。 字符处理比上面的简单示例要多得多。 在下面的评论中，JF Sebastian提供了许多其他重要的链接。

需要解决的几个问题是规范化。 例如，你的面试官是否关心当给出两个字符串时，一个只包含一个Ç而另一个包含一个C后跟一个COMBINING MARK CEDILLA BELOW，它们是否相同？ 它们代表相同的字符 ，但是一个使用一个代码点，另一个使用两个。