如何對字符串進行排序，使字符串在C++中彼此接近？

這會是真的在Java中實現的，因爲你可以使用比較器和內置的方法，以字符數組這樣的字符串進行排序和比較：如何對字符串進行排序，使字符串在C++中彼此接近？

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++等價物肯定是一種選擇。有沒有其他聰明的方法？

來源

2012-01-24 GrowinMan

一個兩級的方法：

排序字符串s成一個有序串t，並添加到map<string, vector<string>爲m[t].push_back(s);的條目。然後地圖的每個條目都是一個相互對立的字符串的向量。

你可能在一個單一的平面multimap中實現相同的邏輯，但這將是更昂貴的（因爲你必須每次排序字符串）;或者你可以製作一個比較器，按字典順序將排序後的字符串與實際的字符串進行比較，但這又非常昂貴。

來源

2012-01-24 13:59:42

顯然也是最好的方法與您在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>（或將字符串映射到字符串的類似字典）內的此緩存進行維護。

來源

2012-01-24 13:59:14

如何對字符串進行排序，使字符串在C++中彼此接近？

回答

相關問題