NC558 题解 | #相似和#

题意分析

• 给出n个字符串串$s_1,s_2,\mathrm{.}\mathrm{.}\mathrm{.}{s}_{n}s\_1,s\_2,...s\_n$

定义两个字符串$s,ts,t$的相似度$f(s,t)f(s,t)$为他们的最长公共前缀长度

求 ${\sum }_{i=1}^{n\mathrm{-}1}{\sum }_{j=i+1}^{n}f(s_i,s_j)\backslash sum\_\{i=1\}^\{n-1\}\backslash sum\_\{j=i+1\}^nf(s\_i,s\_j)$, 保证所有出现的字符均为'a'~'z'的小写英文字母

思路分析

解法一 暴力法

• 我们直接利用双重for循环枚举两个字符串，然后再一个for循环逐个比较前缀和，累加到答案即可。
• 代码如下
  • 最里面的两个for循环枚举字符串，最多需要枚举,然后外面的循环是$O(n)O(n)$,所以总的时间复杂度为
  • 过程中只开了少数几个变量进行存储，空间复杂度为$O(1)O(1)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param s string字符串vector 
     * @return long长整型
     */
    long long solve(int n, vector<string>& s) {
        // write code here
        long long ans=0;
        // 枚举比较的第一个字符串
        for(int i=0;i<n-1;i++){
            // 枚举第二个比较的字符串
            for(int j=i+1;j<n;j++){
                // 枚举两个待比较的字符串的下标
                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;
    }
};

解法二 字典树+dfs

• 题目中给出了n个字符串的长度，同时题目特地说明了字符串一定是小写字母，其实这就是一个很好的暗示。我们先将字符串放到一棵字典树里面，同时标记每个字符串最后的那个结点，我们称之为终结结点。然后进行DFS找到每个结点的子节点中的终结结点的个数，假设某一个结点的子孙节点总终结结点的个数为x，那么这个结点对答案的贡献就是$\frac{x(x-1)}{2}\backslash frac\{x(x-1)\}\{2\}$.

• 如下图

• 代码如下

  • 构建n个字符串，时间复杂度为所有的字符的个数，所以时间复杂度为
  • 构建字典树的时候需要存储字符指针，树的最深的长度为最长的字符串的长度，所以空间复杂度为$O(26\ast max(S_i))O(26*max(S\_i))$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param s string字符串vector 
     * @return long长整型
     */
    typedef long long ll;
    int tree[30][1000010];  // 存储字典树
    int num[1000010];
    int cnt=0; // 记录有多少个结点
    ll ans=0;
    bool ed[1000010];
    // 将字符串插入字典树里面
    void insert(string s){
        int p=0;
        for(auto x:s){
            // 如果这个指针不存在，那么直接新建一个标号
            if(tree[p][x-'a'+1]==-1){
                tree[p][x-'a'+1]=++cnt;
            }
            p=tree[p][x-'a'+1];
        }
        // 标记这个结点
        ed[p]=true;
    }
    
    // 利用递归求出每个结点的子节点中有多少个是一个字符串的结尾，
    // 假设一个结点的子节点中有x个字符串的结尾，那么对答案的贡献就是x*(x-1)/2
    void dfs(int x){
        num[x]=0;
        if(ed[x]) num[x]++;
        for(int i=1;i<=26;i++){
            if(tree[x][i]==-1) continue;
            dfs(tree[x][i]);
            num[x]+=num[tree[x][i]];
        }
        // 0号结点不要计算
        if(x) ans+=(num[x]-1)*num[x]/2;
    }
    long long solve(int n, vector<string>& s) {
        // write code here
        memset(tree,-1,sizeof(tree));
        memset(ed,false,sizeof(ed));
        for(auto x:s){
            insert(x);
        }
        
        dfs(0);
        return ans;
    }
};