LeetCode14 最长公共前缀

链接: https://leetcode.cn/problems/longest-common-prefix/

题意

编写一个函数来查找字符串数组中的最长公共前缀。

解法

有两种解法
第一种是比较巧妙的，把所有的字符串进行排序
然后比较第一个字符串和最后一个字符串，得出他们的最长前缀即为整个数组的最长公共前缀

第二种方法是建立一棵字典树，分支前的前一位即为最长公共前缀

代码

解法一

class Solution {
public:
    static bool cmp(string& pa, string& pb) {
        return pa < pb;
    }
    string longestCommonPrefix(vector<string>& strs) {
        sort(strs.begin(), strs.end(), cmp);
        string a = strs[0], b = strs.back();
        string res = "";
        for (int i = 0; i < b.size(); i++) {
            if (a[i] == b[i]) {
                res += a[i];
            }
            else {
                break;
            }
        }
        return res;
    }
};

解法二

class TrieNode {
public:
    TrieNode* children[26];
    bool isval;
    int num;
    int idx;
    TrieNode(): num(0), idx(0), isval(0) {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};
class Solution {
public:
    TrieNode* root;
    Solution() {
        root = new TrieNode();
    }
    void insert(string p) {
        TrieNode* now = root;
        for (int i = 0; i < p.size(); i++) {
            int ch = p[i] - 'a';
            if (now -> children[ch]) {
                
            }
            else {
                now -> children[ch] = new TrieNode();
                now -> idx = ch;
                now -> num += 1;
            }
            now = now -> children[ch];
        }
        now -> isval = 1;
    }
    string longestCommonPrefix(vector<string>& strs) {
        for (auto s: strs) {
            insert(s);
        }
        string res = "";
        TrieNode* now = root;
        cout << now -> num << endl;
        while(now -> num == 1 && now -> isval != 1) {
            res += 'a' + now -> idx;
            now = now -> children[now -> idx];
        }
        return res;
    }
};