LeetCode 14. Longest Common Prefix字典树 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）这道题的高效解法：

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

巴特西

LeetCode 14. Longest Common Prefix字典树 trie树学习之公共前缀字符串

最新文章

热门文章

巴特西

LeetCode 14. Longest Common Prefix字典树 trie树 学习之 公共前缀字符串

最新文章

热门文章

LeetCode 14. Longest Common Prefix字典树 trie树学习之公共前缀字符串