如何实现基于猜词结果的候选词筛选算法？

我不是编程专家，现在遇到个技术难题：已经实现了根据猜测词（p）生成和参考词（r）的匹配结果（res）的算法，规则是：

• 若p[i] = r[i]，res[i]为'+'；
• 若p[i]不在r中，res[i]为'/'；
• 若p[i]在r中但位置不对，且没达到该字符的错误匹配上限，res[i]为'|'，否则为'/'。

现在需要从词池中移除不符合res给出的边界条件的词，这些边界条件包括：字符是否属于参考词、字符必须出现的位置、字符不能出现的位置、字符出现的最小次数、字符出现的精确次数。

目前用链表存储词和对应边界，但筛选逻辑写得一团糟，现有updateValidity代码逻辑混乱，求帮忙实现正确的筛选算法，同时推荐合适的数据结构。

// Linked list
struct node
{
    int valid;
    char *boundaries;
    char *data;
    struct node *next;
    struct node *prev;
    struct node *head;
};

void updateValidity(Node L)
{
    Node temp1 = L->next;
    while (temp1 != NULL)
    {

        for (int i = 0; i < wordLenght; i++)
        {

            if (temp1->boundaries != NULL)
            {
                // Number of times the letter appear in the reference word
                int c = 0;
                int d = 0;

                if (strchr(referenceWord, temp1->data[i]) != NULL)
                    c++;
                if (strchr(temp1->data, temp1->data[i]) != NULL)
                    d++;
                if (temp1->boundaries[i] == '/' && c < d)
                {
                    // Number of times the letter appear in the word

                    Node temp2 = L->next;

                    while (temp2 != NULL)
                    {
                        for (int j = 0; j < wordLenght; j++)
                        {
                            if (temp1->data[i] == temp2->data[j])
                            {
                                temp2->valid = 0;
                                break;
                            }
                        }
                        temp2 = temp2->next;
                    }
                }
                // 2
                if (temp1->boundaries[i] == '+')
                {
                    Node temp2 = L->next;
                    while (temp2 != NULL)
                    {
                        if (temp1->data[i] != temp2->data[i])
                        {
                            temp2->valid = 0;
                        }
                        temp2 = temp2->next;
                    }
                }
                // 3
                if (temp1->boundaries[i] == '|')
                {
                    Node temp2 = L->next;
                    while (temp2 != NULL)
                    {
                        if (temp1->data[i] == temp2->data[i])
                        {
                            temp2->valid = 0;
                            break;
                        }
                        temp2 = temp2->next;
                    }
                }
            }
        }

        temp1 = temp1->next;
    }
}

一、数据结构推荐 #

链表在频繁遍历和删除操作时效率很低，推荐用**动态数组（C中可使用char**或自定义数组结构）**存储词池，理由：

1. 随机访问效率高，遍历速度远快于链表；
2. 筛选时可直接标记无效元素，最后一次性清理，或边筛选边将有效元素移到数组前端，操作更简便；
3. 若需频繁增删，也可使用哈希表存储符合特定字符条件的词，但动态数组对固定词池的筛选场景更直接高效。

如果一定要保留链表，建议用你现有的双向链表，但遍历和修改时要注意指针操作的正确性，避免内存泄漏。

二、筛选算法实现 #

先从res、猜测词p、参考词r中提取所有边界规则，再逐个检查词池中的词是否符合所有规则。

步骤1：提取核心规则 #

整理出以下规则集合：

1. 必在指定位置的字符：记录所有res[i] = '+'的位置i和对应字符p[i]；
2. 不能在指定位置的字符：记录所有res[i] = '|'的位置i和对应字符p[i]；
3. 完全不存在的字符：记录所有res[i] = '/'且p[i]不在r中的字符；
4. 字符出现次数限制：
   • 统计r中每个字符的总出现次数count_r[c]；
   • 统计猜测词中res[i] = '+'的字符c的数量count_exact[c]，词池中的词w里c的出现次数需满足count_exact[c] ≤ count_w[c] ≤ count_r[c]；
   • 若res中有c对应的'/'（且c在r中），说明猜测词中c的出现次数超过r，此时词池中的词w里c的出现次数必须等于count_r[c]。

步骤2：基于动态数组的筛选实现 #

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 全局变量（可根据实际场景改为参数传入）
int wordLength;
char* referenceWord;
char* guessWord;
char* res;

// 统计字符在字符串中的出现次数
int countChar(const char* str, char c) {
    int cnt = 0;
    while (*str) {
        if (*str == c) cnt++;
        str++;
    }
    return cnt;
}

// 检查单个词是否符合所有规则
int isWordValid(const char* word) {
    // 规则1：必在指定位置的字符
    for (int i = 0; i < wordLength; i++) {
        if (res[i] == '+' && word[i] != guessWord[i]) {
            return 0;
        }
    }

    // 规则2：不能在指定位置的字符
    for (int i = 0; i < wordLength; i++) {
        if (res[i] == '|' && word[i] == guessWord[i]) {
            return 0;
        }
    }

    // 规则3：完全不存在的字符
    for (int i = 0; i < wordLength; i++) {
        if (res[i] == '/' && strchr(referenceWord, guessWord[i]) == NULL) {
            if (strchr(word, guessWord[i]) != NULL) {
                return 0;
            }
        }
    }

    // 规则4：字符出现次数限制
    int refCount[26] = {0};
    for (int i = 0; i < wordLength; i++) {
        refCount[referenceWord[i] - 'a']++;
    }

    int exactCount[26] = {0};
    for (int i = 0; i < wordLength; i++) {
        if (res[i] == '+') {
            exactCount[guessWord[i] - 'a']++;
        }
    }

    int wordCount[26] = {0};
    for (int i = 0; i < wordLength; i++) {
        wordCount[word[i] - 'a']++;
    }

    for (int c = 0; c < 26; c++) {
        char ch = 'a' + c;
        if (refCount[c] == 0) continue;

        // 检查是否存在该字符的无效'/'标记
        int hasInvalidSlash = 0;
        for (int i = 0; i < wordLength; i++) {
            if (guessWord[i] == ch && res[i] == '/') {
                hasInvalidSlash = 1;
                break;
            }
        }

        if (hasInvalidSlash) {
            if (wordCount[c] != refCount[c]) return 0;
        } else {
            if (wordCount[c] < exactCount[c] || wordCount[c] > refCount[c]) return 0;
        }
    }

    return 1;
}

// 筛选词池，返回新的有效词池数组和大小
char** filterWordList(char** wordList, int listSize, int* newSize) {
    char** validList = malloc(listSize * sizeof(char*));
    int validCount = 0;

    for (int i = 0; i < listSize; i++) {
        if (isWordValid(wordList[i])) {
            validList[validCount++] = strdup(wordList[i]);
        }
    }

    validList = realloc(validList, validCount * sizeof(char*));
    *newSize = validCount;
    return validList;
}

步骤3：基于双向链表的筛选实现 #

typedef struct node Node;

void filterLinkedList(Node* head) {
    Node* current = head->next;
    while (current != NULL) {
        Node* nextNode = current->next; // 提前保存下一个节点，防止删除时丢失
        if (!isWordValid(current->data)) {
            // 从双向链表中删除当前节点
            current->prev->next = current->next;
            if (current->next != NULL) {
                current->next->prev = current->prev;
            }
            // 释放内存（根据实际内存分配情况调整）
            free(current->data);
            free(current->boundaries);
            free(current);
        }
        current = nextNode;
    }
}

三、原有代码问题分析 #

1. 逻辑混乱：遍历每个节点的每个字符后又重复遍历整个链表标记，效率极低；
2. 次数统计错误：用strchr统计字符出现次数是错误的，strchr仅返回第一次出现的位置；
3. 规则处理不完整：未处理字符出现次数的精确/最小限制，仅覆盖了部分位置规则；
4. 标记逻辑错误：遇到'/'就标记所有包含该字符的词，忽略了该字符可能在参考词中但猜测词使用过量的情况。

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