相似和

[编程题]相似和

热度指数：352 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出n个字符串串 $s_1,s_2,...s_n$

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

求 $\sum_{i=1}^{n-1}\sum_{j=i+1}^nf(s_i,s_j)$

保证所有出现的字符均为'a'~'z'的小写英文字母

示例1

输入

3,["niuniu","niumei","niuneng"]

输出

说明

"niuniu"与"niumei"的相似度为3
"niuniu"与"niuneng"的相似度为4
"niumei"与"niuneng"的相似度为3
所以相似度的总和为10

备注:


第一个参数n表示字符串个数
第二个参数s包含n个字符串

算法知识视频讲解

吴代庄

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param s string字符串一维数组 
     * @return long长整型
     */
    public long solve (int n, String[] s) {
        // write code here
        Tree root=new Tree();
        long ans=0;
        for(int i=0;i<n;i++){
            int m=s[i].length();
            Tree tem=root;
            for(int j=0;j<m;j++){
                int ix=s[i].charAt(j)-'a';
                if(tem.res[ix]==null){
                    tem.res[ix]=new Tree();
                }
                
                ans+=tem.res[ix].count;
                tem.res[ix].count++;
                tem= tem.res[ix];
            }
        }
        return ans;
        
    }
}
class Tree{
    Tree[]res;
    int count=0;
    Tree(){
        res=new Tree[26];
    }
}

发表于 2021-06-01 23:17:53 回复(0)

牛客745599318号

字典树 fix

struct TREE{
    TREE * node[26];
    int count;
    TREE(){
        count = 0;
        for(int i=0;i<26;i++){
            node[i] = nullptr;
        }
    }
};
class Solution {
public:
    /**
     * 相似和
     * @param n int整型 
     * @param s string字符串vector 
     * @return long长整型
     */
    long long solve(int n, vector<string>& s) {
        // write code here
        TREE *root = new TREE();
        long long ans = 0;
        for(auto ss : s){
            TREE *p = root;
            for(auto ch : ss){
                if(p->node[ch-'a'] == nullptr){
                    p->node[ch-'a'] = new TREE(); 
                }
                ans += p->node[ch-'a']->count;
                p->node[ch-'a']->count++;
                p = p->node[ch-'a'];
            }
        }
        return ans;
    }
};

发表于 2020-07-23 17:44:36 回复(0)

惜缘_梅西

class Solution:
    def commonLen(self ,str1, str2):
        res = 0
        for i in range(len(str1)-1):
            if str2.startswith(str1[:i+1]):
                res = i+1
            else:
                return res
        return res
    def solve(self , n , s ):
        # write code here
        ans = 0
        for i in range(n-1):
            for j in range(i+1,n):
                ans += self.commonLen(s[i], s[j])
        return ans

运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为30.43%

发表于 2020-07-22 17:32:24 回复(0)