这是一个让我难过的问题(明智的解决方案):
给定一个 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,......
最佳答案
绝对有可能,并不难...但这肯定会生成很多字符串。
首先要注意的是,您事先知道它将生成多少个字符串,因此很容易进行完整性检查 :)
第二个:听起来递归解决方案很容易(就像许多遍历问题一样)。
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
。
关于c++ - 专家的字符串和字符映射问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2238224/