leetcode_最长公共前缀

本题主要有用暴力循环法和Trie树来做

1、Trie树

 1 class Solution {
 2 public:
 3 typedef struct node {
 4     char ch;
 5     int branch;    //记录分支树
 6     int times;    //记录这个节点被多少个单词走过，如果times=strs.size()，那他就是前缀之一
 7     node* child[26];//子树
 8 }node, *Trie;
 9 
10 Trie init_Tire() {
11     Trie root = (node*)malloc(sizeof(node));    //给根节点申请内存
12     root->branch = 0;
13     root->times = 0;
14     for(int i = 0; i < 26; i++) root->child[i] = NULL;
15     return root;
16 }
17 
18 void insert_Trie(Trie root, const string str) { //将一个字符串插入到trie树中
19     int n = str.length();    //取该字符串的长度
20     if(n == 0) {    //如果该字符串是空串
21         root->times++;    //
22         return;
23     }
24     int i = 0;
25     int idx;
26     node *p = root; //指向根节点
27     root->times++;
28     while(i < n) {
29         idx = str[i] - 'a';    //取出该字符串的每个字母
30         if(p->child[idx] != NULL) {    //trie树不是应该是纵向的吗？怎么变成横向的了？
31             p = p -> child[idx];
32             p->times++;
33             i++;
34         }
35         else {
36             node* tmp = (node*)malloc(sizeof(node));
37             tmp->ch = str[i];
38             tmp->branch = 0;
39             tmp->times = 1;
40             for(int i = 0; i < 26; i++) tmp->child[i] = NULL;
41             p->branch ++;
42             p->child[idx] = tmp;
43             p = tmp;
44             i++;
45         }
46     }
47 }
48 string longestCommonPrefix(vector<string>& strs) {
49     int n = strs.size();    //总共有多少个字符串？
50     if(n == 0) return "";
51     int i;
52     Trie root = init_Tire();
53     for(i = 0; i < n; i++) insert_Trie(root,strs[i]);
54     i = 0;
55     node* p = root;
56     while(i < strs[0].length() && p-> branch == 1 && p->times == n) {
57         p = p->child[strs[0][i]-'a'];    //遍历这个
58         i++;
59     }
60     if(p->times < n) i--;
61     return strs[0].substr(0,i);
62 }
63 };

2、暴力循环法

暴力循环、、真的好无聊、、

但是为啥速度这么快？

有几个样例比较特殊，比如：

[],[""],["",""]

比如[]，strs[0]就是会指针访问越界，

比如[""]，strs[0][0]同样会指针访问越界，想取strs[0].length()也取不到，所以可能导致无法进入这个循环而导致返回没有返回值

针对这些问题，5、6、12做了防御性编程

 1 class Solution {
 2 public:
 3     string longestCommonPrefix(vector<string>& strs) {
 4         string ans = "";
 5         if(strs.size() == 0) return ans;
 6         if(strs.size() == 1) return strs[0];
 7         for(int i = 0; i < strs[0].length(); i++) {
 8             bool flag = true;
 9             char tmp = strs[0][i];
10             for(int j = 0; j < strs.size(); j++) if(strs[j][i] != tmp) flag = false;
11             if(flag) ans += tmp;
12             else return ans;
13         }
14         return ans;
15     }
16 };