791. 自定义字符串排序/1239. 串联字符串的最大长度

791. 自定义字符串排序

• 相关标签： 字符串

/*

S 所有字符只出现一次 ， 那就是个 哈希表 

感觉 题目应该 是别的意思 。。。 但我用hash 调库完成了。。

*/

#define BUFSIZE 26
#define KEY(x) (x - 'a')
int hm_s[BUFSIZE] = {0};

int cmp(const void *a, const void *b)
{
    return hm_s[KEY(*(char *)a)] - hm_s[KEY(*(char *)b)];
}

char * customSortString(char * S, char * T){
    
    for (int i = 0; i < strlen(S); i++) {
        hm_s[KEY(S[i])] = i;  
    }
    qsort(T, strlen(T), sizeof(char), cmp);
    return T;
}

1239. 串联字符串的最大长度

• 相关标签： 位运算 回溯算法

/*
组合 + 哈希

递归 进行 各自 组合 visited[]

退出条件 ： 全部拼在一起 || 出现重复 


26 个 字母 可以搞 bitmap  int 4*8 = 32 enough

*/

#define BITVALUE(x) (1 << (x - 'a'))
#define BUFLEN 17
#define INVAILD 0x3fffffff

int tranStrToBitV(char *str)
{
    int res = 0;
    int temp = 0;
    for (int i = 0; i < strlen(str); i++) {
        temp = res &  BITVALUE(str[i]);
        if (temp  > 0) {
            return INVAILD;
        } 
        res += BITVALUE(str[i]);
    }
    return res;
}




void recur(char ** arr, int arrSize, int curidx, int *visited, int * arrBitV, int *maxLen, int curLen, int bitmap)
{
    *maxLen = (curLen > *maxLen) ? curLen : *maxLen; // 无论哪种组合 都可以跟新
    if (arrSize - 1 == curidx) {
        return;
    }
    
    for (int i = curidx; i < arrSize; i++) {
        if (visited[i] == 0) {
            if ((bitmap & arrBitV[i]) == 0) { // able to concat
                visited[i] = 1;
                recur(arr, arrSize, i, visited, arrBitV, maxLen, curLen + strlen(arr[i]), bitmap + arrBitV[i]);
                visited[i] = 0;
            }
        }

    }
    return;  
}


int maxLength(char ** arr, int arrSize){
    
    int bitmap = 0;
    
    int visited[BUFLEN] = {0};
    int arrBitV[BUFLEN] = {0};
    
    int bitv;
    int remain = arrSize;
    
    for (int i = 0; i < arrSize; i++) {
        arrBitV[i] = tranStrToBitV(arr[i]);
        if (arrBitV[i] == INVAILD) {
            visited[i] = 1; // 重复单词 
            remain--;
        }
    }
    if (remain == 0) {
        return 0;
    }
    
    if (arrSize == 1) {
        return strlen(arr[0]); // 只有一个的时候 需要直接输出结果
    }
    
    int maxLen = 0;
    
    recur(arr, arrSize, 0, visited, arrBitV, &maxLen, 0, bitmap);
   
    return maxLen;
    

}