相似和

给出n个字符串串,定义两个字符串的相似度为他们的最长公共前缀长度
求

案例
输入：3,["niuniu","niumei","niuneng"]
返回值：10
说明：
"niuniu"与"niumei"的相似度为3
"niuniu"与"niuneng"的相似度为4
"niumei"与"niuneng"的相似度为3
所以相似度的总和为10

方法一 暴力

遍历字符串数组对于第i个字符串需要再遍历i之后的所有字符串与第i字符串进行对比统计.

class Solution {
public:
    long long solve(int n, vector<string>& s) {
        int ans = 0;
        for(int i = 0; i < n; i ++){ // 循环第i个字符串
            for(int j = i + 1; j < n; j ++){ // 遍历第i个字符串之后的所有字符串
                for(int k = 0; k < min(s[i].size(), s[j].size()); k ++){ //判断字符串相同的位数
                    if(s[i][k] == s[j][k]) ans ++;
                    else break;
                }
            }
        }
        return ans;
    }
};

时间复杂度: 对于第i个字符串每次需要与i之后的所有字符进行对比
空间复杂度: 使用若干个变量

方法二 字典树

将所有的字符串存入字典树中并对每一个存入的字符位置进行计数,之后遍历字符串数组一一匹配答案,对于第i个字符串找寻时只需要将每次的结点值减取i这个位数（即字符串在数组的第几位）即可，详见如图

class Solution {
public:
    int tree[1000010][30], cnt[1000010];
    int idx = 0;
    int push(string a, int ff, int id){ //字典树
        int p = 0, res = 0;
        for(int i = 0; i < a.size(); i ++){//将字符存入字符树中
            int ss = a[i] - 'a';
            if(!tree[p][ss]) tree[p][ss] = ++ idx;
            p = tree[p][ss];
            if(ff) cnt[p] ++; //对于每一位记录过的值进行次数统计
            res += max(cnt[p] - id, 0); //计算当前值对于总体的贡献
        }
        return res;
    }
    long long solve(int n, vector<string>& s) {
        // write code here
        int ans = 0;
        for(int i = 0; i < n; i ++) push(s[i], 1, 0);
        for(int i = 0; i < n; i ++) {
            ans += push(s[i], 0, i + 1);
        }
        cout <<endl;
        return ans;
    }
};

时间复杂度: 存储字符串到字典树与读取的复杂度
空间复杂度: 字典树的节点存储以及字符的访问次数