ACM_Someone like you

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

#define MAX 30    //the total number of alphabet is 26, a...z

struct DicTrie{
    bool isTerminal;//是否是單詞結(jié)束標(biāo)志
    int  count;     //當(dāng)前字符串出現(xiàn)次數(shù)
    int  branchCount;    //計(jì)數(shù)當(dāng)前節(jié)點(diǎn)的孩子數(shù)
    struct DicTrie *next[MAX ]; //每個(gè)節(jié)點(diǎn) 最多 有 MAX 個(gè)孩子節(jié)點(diǎn) 結(jié)構(gòu)體嵌套
};


int insertTrie(struct DicTrie *root ,char *targetString)
{
    if (!targetString) {
        return 0;
    }
    int len = strlen(targetString);
    if (len <= 0) {
        return 0;
    }
    struct DicTrie *head = root;
    for (int i = 0; i < len; i ++) {
        int res = (int)(targetString[i] - 'a');//當(dāng)前小寫字母對(duì)應(yīng)數(shù)字
        if (head->next[res] == NULL) { //如果是空節(jié)點(diǎn)
            head->next[res] = (struct DicTrie *)malloc(sizeof(struct DicTrie));//new DicTrie;//則插入新節(jié)點(diǎn)元素
            head = head->next[res]; //更新頭指針 并初始化
            head->count = 0;        //
            for (int j = 0; j < MAX; j ++) {
                head->next[j] = NULL;
                head->isTerminal = false;
            }
            head->branchCount = 1;//一個(gè)分支
        } else {
            head = head->next[res];
            head->branchCount ++;//分支累計(jì)
        }
    }
    head->count ++;//每次插入一個(gè)，響應(yīng)計(jì)數(shù)都增加1
    head->isTerminal = true;
    return head->count;
}

char* longestCommonPrefix(char** strs, int strsSize) {
    
    int len = strsSize;
    //邊界處理
    if (len == 0) {
        return "";
    }
    if (len == 1) {
        return strs[0];
    }
    //組織字典樹(shù)
    struct DicTrie *root = NULL;
    root = (struct DicTrie *)malloc(sizeof(struct DicTrie));
    root->count = 0;
    root->branchCount = 0;
    for (int  i = 0; i < MAX; i ++) {
        root->next[i] = NULL; // 空節(jié)點(diǎn)
        root->isTerminal = false; //
    }
    //
    for (int i = 0;i < len; i ++) {
        insertTrie(root, strs[i]);
    }
    //
    int preIndex = 0;
    
    struct DicTrie *head = root;
    bool isFlag = false;
    int i = 0;
    int count = strlen(strs[0]);//任意一字符串都可以 從strs[0]中查即可
    for (preIndex = 0; preIndex< count; preIndex ++) {
        int targetIndex = strs[0][preIndex] - 'a';
        head = head->next[targetIndex];
        if (head->branchCount == len) {
            i ++;//拿到合法前綴的計(jì)數(shù)
            isFlag = true;
        }
    }
    if (isFlag) {
        preIndex = i;
    } else {
        preIndex = 0;
    }
    strs[0][preIndex] = '\0';
    return  strs[0];
}

int main(int argc, const char * argv[]) {
    // insert code here...
    char *s[30]= {"dog","dracecar","dcar"};
   // char *s[30]= {"flower","flow","flight"};
    char *str = longestCommonPrefix(s,3);
    printf("%s",str);
    return 0;
}