我目前正在研究一个编码问题:
给定一个字符串数组,返回所有为字谜的字符串组
例如:
{asch, scah, bva, vba, soa}
返回{ {asch, scah}, {bva, vba}, {soa}}
为了在小于O(n^2)的时间内解决这个问题,我们应该首先对每个单词进行排序,如果排序的单词相同,则将排序的单词分组在一个集合中。
我想使用二维hashmap。
map<string, map<int,string>> container;
使用这个二维哈希映射,第一个键是排序后的单词,第二个键是它在原始序列中的索引,值是原始单词。
for(int i=0; i<sequence.size();i++)
{
string original_word = sequence[i];
string sorted_word = original_word;
sort(sorted_word.begin(),sorted_word.end());
container[sorted_word][i] = original_word;
}
在此循环之后,我相信所有必须具有相同sorted_word的字谜将被分组到hashmap的第一级。
我的问题是,我应该如何编写代码,以获得具有相同sorted_word的集合?
for( iterator itr = container.begin(); itr != container.end(); itr++)
{
auto grouped_words = itr.second(); // what is the data type of grouped_word here?
}
如有不妥之处请指正。谢谢。 我想这里有一个错误:
vector<string, vector<int,string>> container; // ???
在你的问题中你谈到了哈希映射,我想你的意思是:
unordered_map<string, unordered_map<int,string>> container;
在本例中,您可以这样使用结果:
for( auto itr = container.begin(); itr != container.end(); itr++)
{
auto &grouped_words = itr->second; // prefer a reference
cout << itr->first<<": ";
for (auto &x : grouped_words) {
cout << "t" << x.first << ":"<< x.second<<endl;
}
}
这里有一个现场演示。
Edit: grouped_words
(这里)是对unordered_map<int, string>
的引用