2

真的要在 Java 中实现，因为您可以使用 Comparator 和内置方法对字符数组进行排序并比较字符串，如下所示：

public class AnagramComparator implements Comparator<String> {
 public String sortChars(String s) {
   char[] content = s.toCharArray();
   Arrays.sort(content);
   return new String(content);
 }

public int compare(String s1, String s2) {
   return sortChars(s1).compareTo(sortChars(s2));
 }
}

但我想知道如何在 C++ 中实现这一点？编写与上述 Java 代码中使用的内置方法等效的 C++ 代码绝对是一种选择。还有其他智能方法吗？

4

2 回答 2

5

显而易见的也是最好的方法与您在 Java 中选择的方法非常相似：实现自定义比较器。

在 C++ 中，这是小于谓词的一种特殊化：

struct less_than_sorted_anagram {
    bool operator ()(std::string a, std::string b) {
        std::sort(a.begin(), a.end());
        std::sort(b.begin(), b.end());
        return a < b;
    }
};

并这样称呼它：

std::vector<std::string> range;
// …
std::sort(range.begin(), range.end(), less_than_sorted_anagram());

但是（就像您的 Java 代码一样）这是非常低效的，因为必须重复计算排序的字谜。只计算一次（比如在第一次使用时）并缓存它们会更有效。

例如，您可以在less_than_sorted_anagram谓词中将此缓存维护为 a std::map<std::string, std::string>（或类似的字典，将字符串映射到字符串）。

于 2012-01-24T13:59:14.217 回答
1

两级方法：

将字符串排序s为已排序的字符串t，并将条目添加到map<string, vector<string>as m[t].push_back(s);。然后映射的每个条目是相互依序的字符串的向量。

您可以在单个平面多图中实现相同的逻辑，但这会更加昂贵（因为您每次都必须对字符串进行排序）；或者您可以制作一个比较器，首先按字典顺序比较已排序的字符串，然后再比较实际的字符串，但这又是非常昂贵的。

于 2012-01-24T13:59:42.227 回答