题解 | 小红的数位删除

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 存储生成的子序列信息
typedef struct 
{
    long long val;
    int ops;
} Node;
Node listA[1024], listB[1024];
int countA = 0, countB = 0;
// 递归函数：s是原串，index是当前位置，current是目前拼出的数，ops是删除次数
void dfs(char* s, int index, long long current, int ops, Node* list, int* count, int hasDigit) 
{
    if (s[index] == '\0') 
    {
        if (hasDigit && current > 0) 
        { // 只要不是空，且是正整数
            list[*count].val = current;
            list[*count].ops = ops;
            (*count)++;
        }
        return;
    }
    // 选择1：保留当前字符
    // 注意处理前导零：如果当前是0且之前没数，则不构成有效正整数的前缀（除非后面还有数）
    dfs(s, index + 1, current * 10 + (s[index] - '0'), ops, list, count, 1);
    // 选择2：删除当前字符
    dfs(s, index + 1, current, ops + 1, list, count, hasDigit);
}
int main() 
{
    char s1[10], s2[10];
    scanf("%s %s", s1, s2);
    // 生成A和B的所有可能结果
    dfs(s1, 0, 0, 0, listA, &countA, 0);
    dfs(s2, 0, 0, 0, listB, &countB, 0);
    int min_ops = 100;
    // 暴力比对两组结果
    for (int i = 0; i < countA; i++) 
    {
        for (int j = 0; j < countB; j++) 
        {
            long long a = listA[i].val;
            long long b = listB[j].val;
            if (a % b == 0 || b % a == 0) 
            {
                int total = listA[i].ops + listB[j].ops;
                if (total < min_ops) min_ops = total;
            }
        }
    }
    printf("%d\n", (min_ops == 100) ? -1 : min_ops);
    return 0;
}

这道题想到了利用dfs（选当前位置字符和不选当前位置字符两种情况），由于不太熟练（结合结构体求解），最终由AI来完成的，这种方法还是比较容易看懂的，