c++ - 从过去的工作面试中检查我的字谜代码

Question

前段时间有以下面试问题，但基本语法太卡了，我没能继续前进(一旦肾上腺素开始发挥作用，编码就会消失。)

给定一个字符串列表，返回一个字符串集列表，这些字符串集是输入集的变位词。即“dog”，“god”，“foo”应该返回 {“dog”，“god”}。之后，我自己创建了代码作为健全性检查，它已经存在了一段时间。我欢迎就此发表意见，看看我是否遗漏了什么，或者我是否可以更有效地完成它。借此机会提高自己并学习其他技术:

void Anagram::doWork(list input, list> &output)
{
  typedef list < pair < string, string>> SortType;
  SortType sortedInput;<br/>
  // sort each string and pair it with the original
  for(list< string >::iterator i = input.begin(); i != input.end(); ++i)
  {
    string tempString(*i);
    std::sort(tempString.begin(), tempString.end());
    sortedInput.push_back(make_pair(*i, tempString));
  }<br/>
  // Now step through the new sorted list
  for(SortType::iterator i = sortedInput.begin(); i != sortedInput.end();)
  {
    set< string > newSet;<br/>
    // Assume (hope) we have a match and pre-add the first.
    newSet.insert(i->first);<br/>
    // Set the secondary iterator one past the outside to prevent
    // matching the original
    SortType::iterator j = i;
    ++j;<br/>
    while(j != sortedInput.end())
    {
      if(i->second == j->second)
      {
        // If the string matches, add it to the set and remove it
        // so that future searches need not worry about it
        newSet.insert(j->first);
        j = sortedInput.erase(j);
      }
      else
      {
        // else, next element
        ++j;
      }
    }<br/>
    // If size is bigger than our original push, we have a match 
    // - save it to the output
    if(newSet.size() > 1)
    {
       output.push_back(newSet);
    }<br/>
    // erase this element and update the iterator
    i = sortedInput.erase(i);
  }
}

在查看评论并了解更多信息后，这是第二遍:

void doBetterWork(list input, list> &output)
{
  typedef std::multimap< string, string > SortedInputType;
  SortedInputType sortedInput;
  vector< string > sortedNames;<br/>
  for(vector< string >::iterator i = input.begin(); i != input.end(); ++i)
  {
    string tempString(*i);
    std::sort(tempString.begin(), tempString.end());
    sortedInput.insert(make_pair(tempString, *i));
    sortedNames.push_back(tempString);
  }<br/>
  for(list< string >::iterator i = sortedNames.begin(); i != sortedNames.end(); ++i)
  {
    pair< SortedInputType::iterator,SortedInputType::iterator > bounds;
    bounds = sortedInput.equal_range(*i);<br/>
    set< string > newSet;
    for(SortedInputType::iterator j = bounds.first; j != bounds.second; ++j)
    {
      newSet.insert(j->second);
    }<br/>
    if(newSet.size() > 1)
    {
      output.push_back(newSet);
    }<br/>
    sortedInput.erase(bounds.first, bounds.second);
  }
}<p></p>

<p></p>

Answer 1

对字谜进行分组的最佳方法是将字符串映射到某种直方图表示形式。

 FUNCTION histogram
 [input] -> [output]

 "dog"   -> (1xd, 1xg, 1xo)
 "god"   -> (1xd, 1xg, 1xo)
 "foo"   -> (1xf, 2xo)

基本上，通过对字符串进行线性扫描，您可以生成直方图表示它包含的每个字母的数量。一个小的、有限的字母表使这更容易(例如，使用 A-Z，您只有一个包含 26 个数字的数组，每个字母一个)。

现在，字谜只是具有相同直方图的单词。

然后您可以拥有一个 multimap 数据结构，将直方图映射到具有该直方图的单词列表。

MULTIMAP
[key]           => [set of values]

(1xd, 1xg, 1xo) => { "dog", "god" }
(1xf, 2xo)      => { "foo" }

规范形式技巧

除了处理直方图，您还可以处理 "canonical form"的字符串。基本上，您为每个字符串定义其规范形式，如果两个词具有相同的规范形式，则它们是变位词。

一种方便的规范形式是对字符串中的字母进行排序。

FUNCTION canonize
[input]  -> [output]

"dog"    -> "dgo"
"god"    -> "dgo"
"abracadabra" -> "aaaaabbcdrr"

请注意，这只是直方图方法之后的一步:您实际上是在做 counting sort对字母进行排序。

这是针对您的问题的实际编程语言中最实用的解决方案。

复杂性

生成单词的直方图/规范形式实际上是 O(1)(有限的字母表大小，有限的最大单词长度)。

通过良好的哈希实现，get 和 put 到 multimap 上是 O(1)。

您甚至可以有多个多重映射，每个单词长度一个。

如果有 N 个单词，那么将所有单词放入 multimaps 就是 O(N)；然后输出每个 Anagram 组只是将值转储到多重映射中。这也可以在 O(N) 中完成。

这肯定比检查每对单词是否是变位词(O(N^2) 算法)要好。