在 C++ 中，如何对字符串进行排序以使字谜词彼此靠近？

发布于 2024-12-28 19:24:36 字数 472 浏览 5 评论 0 原文

这确实是用 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++ 绝对是一种选择。还有其他聪明的办法吗？

原文

It'd be really to implement in Java, since you could use the Comparator and the built in methods to sort character arrays and compare strings like this:

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

But I'm wondering how would one go about implementing this in C++?
Coding the C++ equivalent of the built-in methods used in the above Java code is definitely one option. Is there any other intelligent way?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

尘世孤行 2025-01-04 19:24:36

最明显也是最好的方法与您在 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 谓词中将此缓存维护为 std::map （或将字符串映射到的类似字典）字符串）。

The obvious and also the best way is quite similar to the one you chose in Java: implement a custom comparer.

In C++, that’s a specialisation of a less-than predicate:

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;
    }
};

And call it like this:

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

But (just like your Java code) this is quite inefficient since the sorted anagrams have to be computed repeatedly. It would be much more efficient to only compute them once (on first use, say) and cache them.

You could for instance maintain this cache inside the less_than_sorted_anagram predicate as a std::map<std::string, std::string> (or a similar dictionary mapping strings to strings).