c++ - 最小唯一字符

Question

REF:此链接上的问题 5:http://www.geeksforgeeks.org/directi-programming-questions

给定:两个字符串 X 和 Y，只有一个可能的操作，即交换 X 和 Y 的对应字母(即 X[i] 和 Y[i])，可以执行任意次数。

n(X) : number of unique characters in X
n(Y) : number of unique characters in Y

问题:通过使用交换操作，找到 max(n(X),n(Y)) 的最小可能值

INPUT:
ababa
babab

OUTPUT:
1
--------------------
INPUT:
abaaa
baaac

OUTPUT:
2

请帮助我纠正我的解决方案或用更好的方法解决这个问题。 我的方法(适用于第一个和许多其他测试用例，但不适用于第二个):

    for(int i=0; i<x;i++)
    {
        if((count1[st1[i]]!=-1)||(count2[st2[i]]!=-1))
        {
            if(st1[i]!=st2[i])
            {
            if(count1[st1[i]]!=-1)
            count1[st1[i]]++;

            if(count2[st2[i]]!=-1)
            count2[st2[i]]++;
            }
            else 
            {
            ans++;
            count1[st1[i]]=-1;
            count2[st1[i]]=-1;
            }
        }
    }


  for(int i=97;i<123;i++)
  {
    if(count1[i]>0)
    c1++;
    if(count2[i]>0)
    c2++;
    if((count1[i]>0)&&(count2[i]>0))
    com++;
  }

    un = max(c1,c2);
    ans+= un-com/2;
    printf("%lld\n",ans);

Answer 1

我不确定我是否理解您的算法，但这里是蛮力版本，适用于最多 64 个符号长度的字符串:

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

#define max(a,b) (a >= b ? a : b)
#define min(a, b) (a <= b ? a : b)
#define swap(a, b, idx) (a[idx] = a[idx] ^ b[idx] ^ (b[idx] = a[idx]))

int unique(char*a) {
    char c[256] = { 0 };
    int u = 0;
    while (*a) {
        u += (c[*a] == 0);
        c[*a++] = 1;
    }
    return u;
}

void swapWithMask(char* a, char* b, unsigned long int mask, int l) {
    for (int j = 0; j < l; j++)
        if ((mask & (1 << j)) != 0)
            swap(a, b, j);
}

int minUnique(char*oa, char*ob) {
    int l = strlen(oa);
    int minu = l;

    char *a = malloc(l + 1);
    strcpy(a, oa);
    char *b = malloc(l + 1);
    strcpy(b, ob);

    unsigned long int m = (1 << l);
    for (unsigned long int i = 0; i < m; i++) {
        swapWithMask(a, b, i, l);
        minu = min(max(unique(a), unique(b)), minu);
        swapWithMask(a, b, i, l);
    }

    free(b);
    free(a);
    return minu;
}

int main(void) {
    puts((minUnique("directi", "itcerid") == 4) ? "ok" : "fail");
    puts((minUnique("ababa", "babab") == 1) ? "ok" : "fail");
    puts((minUnique("abaaa", "baabb") == 2) ? "ok" : "fail");
    return 0;
}