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

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

一种方法是使用 diagonalization :

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

另一种方法是复制集合中最长的字符串并将任何字符附加到拷贝中。这个新字符串将不同于集合中的每个字符串。

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