C++字符串数组字符比较：函数f()实现正确性咨询

需求回顾 #

函数f()接收字符串数组A和整数k（数组长度大于k），当且仅当数组中每个下标≥k的字符串，都与其前k个字符串分别至少有一个共同字符时返回true。

示例：当A=["abcd", "efgh", "abe", "af", "bef"]，k=2时返回true：

• "abe"与"abcd"（共字符a/b）、"efgh"（共字符e）均有共同字符；
• "af"与"efgh"（共字符f）、"abe"（共字符a）均有共同字符；
• "bef"与"abe"（共字符b/e）、"af"（共字符f）均有共同字符。

你的代码问题 #

你提供的代码存在多处逻辑错误，完全不符合需求：

bool f(char A[][5], int k)
{
    while(k<5)
    {
        for(int j=0; j<5; j++)
        {
            for(int y=0; y<5; y++)
            {
                if( A[k][j]==A[k-1][y] && A[k][j]==A[k-2][y] )
                {
                    return true;
                }
            }
        }
        k++;
    }
    return false;
}

int main()
{
    char A[5][5]={"abcd", "efgh", "abe", "af", "bef"};
    
    cout << f(A,2);

    return 0;
}

错误点：

1. 循环范围硬编码：用k<5判断循环结束，仅适用于数组长度为5的场景，不具备通用性。
2. 字符匹配逻辑错误：A[k][j]==A[k-1][y] && A[k][j]==A[k-2][y]要求当前字符同时和前两个字符串的同一位置字符相等，这和“至少有一个共同字符”的要求完全不符——共同字符不需要位置相同，也不需要同时和前k个字符串共享同一个字符，只需要和每个前k个字符串分别有至少一个重叠字符即可。
3. 提前返回逻辑错误：只要找到一个满足条件的字符就直接返回true，但需求要求所有符合条件的字符串都满足规则，只要有一个不满足就应该返回false，正确逻辑应该是检查所有不满足的情况，一旦发现就返回false，全部通过再返回true。
4. 未正确遍历前k个字符串：比如当k=2时，需要检查索引2、3、4的字符串，但你的代码对每个k的检查逻辑完全错误，没有覆盖所有前k个字符串的校验。

正确实现思路与代码 #

核心思路：

• 遍历数组中从索引k开始的每个字符串curr_str；
• 对每个curr_str，逐一检查它的前k个字符串（即索引i-k到i-1的字符串）；
• 对每个前序字符串，判断是否和curr_str有共同字符；
• 如果任何一个前序字符串和curr_str没有共同字符，直接返回false；
• 所有字符串都通过检查后返回true。

实现代码（哈希集合版） #

用字符哈希集合快速判断字符是否存在，提升效率：

#include <iostream>
#include <unordered_set>
#include <cstring>
using namespace std;

bool hasCommonChar(const char* s1, const char* s2) {
    unordered_set<char> chars;
    // 把s1的所有字符加入集合
    for (int i = 0; s1[i] != '\0'; i++) {
        chars.insert(s1[i]);
    }
    // 检查s2是否有字符在集合中
    for (int i = 0; s2[i] != '\0'; i++) {
        if (chars.count(s2[i])) {
            return true;
        }
    }
    return false;
}

bool f(char A[][5], int k, int arrLen) {
    // 遍历从k开始的每个元素
    for (int i = k; i < arrLen; i++) {
        // 检查当前元素的前k个元素
        for (int j = i - k; j < i; j++) {
            if (!hasCommonChar(A[i], A[j])) {
                // 只要有一个前序字符串无共同字符，直接返回false
                return false;
            }
        }
    }
    // 所有元素都满足条件
    return true;
}

int main() {
    char A[5][5] = {"abcd", "efgh", "abe", "af", "bef"};
    // 传入数组长度5
    cout << f(A, 2, 5) << endl;
    return 0;
}

实现代码（数组标记版） #

如果不想用哈希集合，也可以用数组记录字符（ASCII字符范围有限），更贴合C语言风格：

#include <iostream>
#include <cstring>
using namespace std;

bool hasCommonChar(const char* s1, const char* s2) {
    bool charExists[256] = {false};
    for (int i = 0; s1[i] != '\0'; i++) {
        charExists[(unsigned char)s1[i]] = true;
    }
    for (int i = 0; s2[i] != '\0'; i++) {
        if (charExists[(unsigned char)s2[i]]) {
            return true;
        }
    }
    return false;
}

bool f(char A[][5], int k, int arrLen) {
    for (int i = k; i < arrLen; i++) {
        for (int j = i - k; j < i; j++) {
            if (!hasCommonChar(A[i], A[j])) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    char A[5][5] = {"abcd", "efgh", "abe", "af", "bef"};
    cout << f(A, 2, 5) << endl;
    return 0;
}

关键说明 #

• 新增数组长度参数arrLen，让函数可以处理任意长度的数组，不再依赖硬编码的5；
• hasCommonChar函数专门负责判断两个字符串是否有共同字符，逻辑清晰，可复用；
• 主逻辑采用反向判断：只要发现一个不满足条件的情况就返回false，全部通过才返回true，符合需求中“当且仅当所有情况满足”的要求；
• 字符检查不依赖位置，只关心字符是否存在，完全符合需求描述。

内容的提问来源于stack exchange，提问作者Giuseppe