题解 | #相似和#

思路：

题目的主要信息：

• 字符串的相似度定义为两个字符串的相同字符前缀长度
• 对于n个字符串，求任意两个字符串的相似度，并求总和
• 只出现小写字母a-z

方法一：暴力法
具体做法：

class Solution {
public:
    int similarity(string& s1, string& s2){ //计算两个字符串相似度的函数
        int len1 = s1.length();
        int len2 = s2.length();
        int n = min(len1, len2); //遍历较小的
        int res = 0;
        for(int i = 0; i < n; i++){
            if(s1[i] == s2[i])  //前缀相似字符数
                res++;
            else
                break;
        }
        return res;
    }
    long long solve(int n, vector<string>& s) {
        long long res = 0;
        for(int i = 0; i < n; i++){ //找到任意两个字符串
            for(int j = i + 1; j < n; j++){
                res += similarity(s[i], s[j]);
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，外层循环为，内存循环为，个计算相似度的函数相当于遍历所有字符串长度和，即
• 空间复杂度：，常数空间

方法二：字典树
具体做法：
因为要对每一个字符串和剩余的全部字符串比较，我们可以创建字典树，沿着树枝比较，每次重复加路径上的计数即可。如图所示简约字典树，只有abc三个字母：

class Solution {
public:
    struct Tree{
        Tree* letter[26]; //26个小写字母
        int count;  //前缀计数
        Tree(){    //初始化函数
            for(int i = 0; i < 26; i++)
                letter[i] = NULL;
            count = 0;
        }
    };
    long long solve(int n, vector<string>& s) {
        long long res = 0;
        Tree* root = new Tree();
        for(int i = 0; i < n; i++){
            Tree* p = root;
            for(int j = 0; j < s[i].length(); j++){
                if(p->letter[s[i][j] - 'a'] == NULL) //如果对应字符为空，创建新树
                    p->letter[s[i][j] - 'a'] = new Tree();
                p = p->letter[s[i][j] - 'a']; //进入子树
                res += (long long)(p->count); //累加
                p->count++; //前缀计数
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，相当于遍历所有的字符串
• 空间复杂度：，树空间最深处为最长字符串的长度