你如何对字符串进行排序,使得字谜在C++中彼此接近？

Question

它实际上是用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++等价物绝对是一种选择.还有其他智能方式吗？

Answer 1

显而易见且最好的方式与您在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<std::string, std::string>(或将字符串映射到字符串的类似字典).