字典树 trie树 学习之 公共前缀字符串

所有字符串的公共前缀最长字符串

特点：（1）公共所有字符串前缀 （好像跟没说一样。。。）

         （2）在字典树中特点：任意从根节点触发遇见第一个分支为止的字符集合即为目标串

参考问题：https://leetcode.com/problems/longest-common-prefix/description/

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.

题干容易理解，翻译略

实现步骤

1.构建字典树

当任意一字符串中的当前节点的branchCount等于输入的单词个数时候，那么这个节点就是在最长前缀里

C 语言解法：

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

struct DicTrie{
    bool isTerminal;//是否是单词结束标志
    int  count;     //当前字符串出现次数
    int  branchCount;    //计数当前节点的孩子数
    struct DicTrie *next[MAX ]; //每个节点 最多 有 MAX 个孩子节点 结构体嵌套
};


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');//当前小写字母对应数字
        if (head->next[res] == NULL) { //如果是空节点
            head->next[res] = (struct DicTrie *)malloc(sizeof(struct DicTrie));//new DicTrie;//则插入新节点元素
            head = head->next[res]; //更新头指针 并初始化
            head->count = 0;        //
            for (int j = 0; j < MAX; j ++) {
                head->next[j] = NULL;
                head->isTerminal = false;
            }
            head->branchCount = 1;//一个分支
        } else {
            head = head->next[res];
            head->branchCount ++;//分支累计
        }
    }
    head->count ++;//每次插入一个，响应计数都增加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];
    }
    //组织字典树
    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; // 空节点
        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 ++;//拿到合法前缀的计数
            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;
}

 

其实，我这道题在思路上没有任何问题，工作用的都是面向对象语言，面向过程C，纯C少了，所以代码不符合提交要求

比如创建结构体 我自己写 就是new DicTrie,但是纯C种 用malloc.

还有字符串截取。。。都得自己一点点面向过程敲。不然就是运行错误。

 

最后

（1）解这道题的目的：

（2）拓宽思路后缀数组：

（3）这道题的高效解法：

该休息了，剩下的后续补充