生成与集合中的字符串不匹配的字符串

Question

一个奇怪的问题 - 如何生成一组与字符串中的任何字符串不匹配的字符串？我不想对字符串做任何假设.解决方案理想情况下是基于STL的,但并非必须如此

例:

vector<string> strings;
/*...*/
string unMatching = generateUnmatching(strings); //this is the function I want

assert(find(strings.begin(), strings.end(), unMatching) == strings.end());

Answer 1

一种方法是使用对角化:

• 从空字符串s开始.
• 查看集合中第一个字符串的第一个字符.选择除此之外的任何字符,并将其附加到s.
• 查看集合中第二个字符串的第二个字符.选择除此之外的任何字符,并将其附加到s.
• 遵循相同的模式,始终查看第i个字符串的第i个字符并为s添加不同的字符.
• 当您完成集合中的最后一个字符串时,s将至少在一个位置与集合中的每个字符串不同.

另一种方法是复制集合中最长的字符串,并将任何字符附加到副本.这个新字符串将与集合中的每个字符串不同.

有各种其他方法可以完成同样的事情.为问题添加一些约束将有助于选择对您的问题最有意义的算法.例如,您可能决定生成与集合中的任何字符串不匹配的最短字符串,或者具有最低lexigraphic排序值的字符串,或者与其他字符串共同具有最小字符数的字符串,或者......