题解 | #相似和#

题意整理

• 给定一个字符串数组。
• 求字符串数组中的字符串两两匹配的最长公共前缀之和。

方法一（暴力法）

1.解题思路

直接两层循环遍历所有的字符串组合，然后计算每个组合的最长公共前缀。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param s string字符串一维数组 
     * @return long长整型
     */
    public long solve (int n, String[] s) {
        //初始化相似和
        long sum=0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                //计算所有组合的最长公共前缀之和
                sum=sum+preFix(s[i],s[j]);
            }
        }
        return sum;
    }

    //计算两个字符串的最长公共前缀
    private int preFix(String s1,String s2){
        int res=0;
        int n=Math.min(s1.length(),s2.length());
        //遍历较短的字符串的长度
        for(int i=0;i<n;i++){
            //如果相等，则公共前缀长度加一
            if(s1.charAt(i)==s2.charAt(i)){
                res++;
            }
            else{
                break;
            }
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：从n个字符串中任取两个字符串的组合数是 ，而计算每个组合的最长公共前缀，最坏情况下需要次 ， 是所有字符串的长度之和，于是总共需要遍历次， 所以时间复杂度是 。
• 空间复杂度：需要额外常数级别的内存空间，所以空间复杂度是。

方法二（字典树）

1.解题思路

可以通过字典树存储每个节点访问次数，如果是相同节点，则加上之前该节点的访问次数等于当前所有字符串的相似和。

动图展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param s string字符串一维数组 
     * @return long长整型
     */
    public long solve (int n, String[] s) {
        //初始化字典树
        Trie trie=new Trie();
        for(int i=0;i<n;i++){
            //向字典树插入字符串
            trie.insert(s[i]);
        }

        //返回相似和
        return trie.getSum();
    }

}

class Trie{
    //子节点数组
    Trie[] child;
    //每个节点插入次数
    int cnt;
    //记录相似和
    long sum;

    Trie(){
        this.child=new Trie[26];
        this.cnt=0;
    }

    public void insert(String s){
        Trie node=this;
        for(char c:s.toCharArray()){
            if(node.child[c-'a']==null){
                node.child[c-'a']=new Trie();
            }
            node=node.child[c-'a'];
            //每次加上之前该节点的插入次数
            sum+=node.cnt;
            node.cnt++;
        }
    }

    //获取相似和
    public long getSum(){
        return sum;
    }
}

3.复杂度分析

• 时间复杂度：假设 是所有字符串的长度之和，字典树中插入的节点个数最多为，所以时间复杂度是 。
• 空间复杂度：需要额外大小为的空间存储节点，而每个节点还自带一个child数组(数组大小为26)，所以空间复杂度是 。