古茹的字符串和字符映射问题

Question

这是一个让我难以理解的问题(解决方案明智):

给定str S,应用字符映射Cm = {a=(m,o,p),d=(q,u),...}并使用C或C++打印出所有可能的组合.

字符串可以是任意长度,字符映射的数量会有所不同,并且不会有任何映射到另一个映射的映射(从而避免循环依赖).

例如:abba带有映射的字符串a=(e,o), d=(g,h), b=(i)将打印:

abba,ebba,obba,abbe,abbo,ebbe,ebbo,obbe,obbo,aiba,aiia,abia,eiba,eiia,...... 

Answer 1

绝对有可能，并不是真的很困难......但这肯定会生成很多字符串。

首先要注意的是，您事先知道它将生成多少个字符串，因此很容易进行一些健全性检查:)

第二：听起来递归解决方案很容易（就像许多遍历问题一样）。

class CharacterMapper
{
public:
  CharacterMapper(): mGenerated(), mMapped()
  {
    for (int i = -128, max = 128; i != max; ++i)
      mMapped[i].push_back(i); // 'a' is mapped to 'a' by default
  }

  void addMapped(char origin, char target)
  {
    std::string& m = mMapped[origin];
    if (m.find(target) == std::string::npos) m.push_back(target);
  } // addMapped

  void addMapped(char origin, const std::string& target)
  {
    for (size_t i = 0, max = target.size(); i != max; ++i) this->addMapped(origin, target[i]);
  } // addMapped

  void execute(const std::string& original)
  {
    mGenerated.clear();
    this->next(original, 0);
    this->sanityCheck(original);
    this->print(original);
  }

private:
  void next(std::string original, size_t index)
  {
    if (index == original.size())
    {
      mGenerated.push_back(original);
    }
    else
    {
      const std::string& m = mMapped[original[index]];
      for (size_t i = 0, max = m.size(); i != max; ++i)
        this->next( original.substr(0, index) + m[i] + original.substr(index+1), index+1 );
    }
  } // next

  void sanityCheck(const std::string& original)
  {
    size_t total = 1;
    for (size_t i = 0, max = original.size(); i != max; ++i)
      total *= mMapped[original[i]].size();

    if (total != mGenerated.size())
      std::cout << "Failure: should have found " << total << " words, found " << mGenerated.size() << std::endl;
  }

  void print(const std::string& original) const
  {
    typedef std::map<char, std::string>::const_iterator map_iterator;
    typedef std::vector<std::string>::const_iterator vector_iterator;

    std::cout << "Original: " << original << "\n";

    std::cout << "Mapped: {";
    for (map_iterator it = mMapped.begin(), end = mMapped.end(); it != end; ++it)
      if (it->second.size() > 1) std::cout << "'" << it->first << "': '" << it->second.substr(1) << "'";
    std::cout << "}\n";

    std::cout << "Generated:\n";
    for (vector_iterator it = mGenerated.begin(), end = mGenerated.end(); it != end; ++it)
      std::cout << "  " << *it << "\n";
  }

  std::vector<std::string> mGenerated;
  std::map<char, std::string> mMapped;
}; // class CharacterMapper


int main(int argc, char* argv[])
{
  CharacterMapper mapper;
  mapper.addMapped('a', "eo");
  mapper.addMapped('d', "gh");
  mapper.addMapped('b', "i");
  mapper.execute("abba");
}

这是输出：

Original: abba
Mapped: {'a': 'eo''b': 'i''d': 'gh'}
Generated:
  abba
  abbe
  abbo
  abia
  abie
  abio
  aiba
  aibe
  aibo
  aiia
  aiie
  aiio
  ebba
  ebbe
  ebbo
  ebia
  ebie
  ebio
  eiba
  eibe
  eibo
  eiia
  eiie
  eiio
  obba
  obbe
  obbo
  obia
  obie
  obio
  oiba
  oibe
  oibo
  oiia
  oiie
  oiio

是的，相当冗长，但是有很多内容不直接参与计算（初始化、检查、打印）。核心方法是next实现递归。