定义两个字符串,的相似度为他们的最长公共前缀长度
求
保证所有出现的字符均为'a'~'z'的小写英文字母
3,["niuniu","niumei","niuneng"]
10
"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]; } }
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; } };
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运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。