博客

/* 
 * 算法思想：
 * 关键是字符串的比较，这个有点坑，没说可以转圈啊，题意也没表现出a可以在z之前。。。
 *
 */

bool cmp_str(char *s1, char *s2){
    int i=0, j=0;
    int val = s1[0] - s2[0];
    int flag = 0;
    
    //printf("s1=%s, s2=%s\n", s1, s2);
    
    while(s1[i] && s2[j]){
        if((s1[i] - s2[j]== val) || 
           (s1[i] - s2[j] == val+26) || 
           (s1[i] - s2[j] == val - 26)){
            
        }else{
            return false;
        }
        
        
        i++;
        j++;
    }
    //printf("true\n");
    return !s1[i] && !s2[j];
}

/* 时间复杂度O(N*N) */
char*** groupStrings(char** strs, int strsSize, int* returnSize, int** columnSizes) {
    int i, j;
    bool *vist = (bool *)malloc(sizeof(bool) * strsSize);
    char *** ret = (char ***)malloc(sizeof(char**) * strsSize);
    int *col_size = (int *)malloc(sizeof(int) * strsSize);
    int ret_index = 0;
    int col_index = 0;
    
    for(i=0; i<strsSize; i++){
        vist[i] = false;
    }
    
    for(i=0; i<strsSize; i++){
        
        if(vist[i]) continue;
        
        vist[i] = true;
        col_index = 0;
        ret[ret_index] = (char **)malloc(sizeof(char *) * strsSize);
        ret[ret_index][col_index++] = strs[i];
        
        for(j=i+1; j<strsSize; j++){
                
            if(cmp_str(strs[i], strs[j])){
                vist[j] = true;
                ret[ret_index][col_index++] = strs[j];
            }          
        }
        col_size[ret_index] = col_index;
        
        ret_index++;
    }
    
    free(vist);
    
    *columnSizes = col_size;
    
    *returnSize = ret_index;
    
    return ret;
    
}