最长合成字符串

如果你比较认可我的解法欢迎帮我点个赞，不足之处请多指教

思想：

如果一个字符串是由数组中其他字符串组成，那么该字符串中的每个字符出现的次数是大于1的

基于以上想法：

• 1将字符串按长度从小到大排列（这里使用冒泡算法）

• 2从数组第一个开始，统计每个字符串中字符出现的次数

• 3遇到的第一个每个字符出现次数都大于1的字符串，那么就将他认为是最大字符串

• 4遇到下一个符合条件的最大字符串，且长度比目前的长度长，那么将它替换为最大字符串

• 5遍历完成，返回最大字符串长度即可

• 时间复杂度 n^2 主要是冒泡算法时间复杂度

• 查找的时间复杂度 n*2max(str.length())

  public int getLongest(String[] str, int n) {
        String maxLenStr="";
        int[] arr=new int[26];
        sort(str);
        for (int i = 0; i <str.length ; i++) {
            String tempStr=str[i];
            int len=tempStr.length();
            int[] brr=new int[len];
            for (int j = 0; j <len ; j++) {
                int index = tempStr.charAt(j) - 'a';
                arr[index]=arr[index]+1;
                if (arr[index]>1){
                    brr[j]=1;
                }
            }
            for (int j = 0; j < len; j++) {
                if (brr[j]<1){
                    break;
                }else if(j==len-1&&maxLenStr.length()<len){
                    maxLenStr=tempStr;
                }
            }
        }
  
        return maxLenStr.length();
    }
    public void sort(String[] str){
        String strTemp;
        for (int i = 0; i < str.length; i++) {
            for (int j = i+1; j <str.length ; j++) {
                int len1=str[i].length();
                int len2=str[j].length();
                if (len1>len2){
                    strTemp=str[i];
                    str[i]=str[j];
                    str[j]=strTemp;
                }
            }
        }
    }

参考高赞答案的Java版

public class LongestString {
    
    public int getLongest(String[] str, int n) {
        // write code here
        Arrays.sort(str, new Comparator<String>(){
            @Override
            public int compare(String o1, String o2)
            {
                return o2.length() - o1.length(); 
            }
        });
        for(int i = 0; i < n ; i++)
        {
            if(other(str, str[i], i ,n))
                return str[i].length();
        }
        return 0;
            
    }
    
    private boolean other(String[] str, String s, int index, int n)
    {
        if(s.length() == 0)
            return true;
        for(int i = index + 1; i < n ; i++)
        {
            if(s.startsWith(str[i]))
            {
                if( other (str, s.substring(str[i].length()), index, n) )
                    return true;
            }
        }
        return false;
    }
}

//思路:先将字符串数组按照字母序排序。然后，采用递归的方式来进行判断。
public class LongestString {
    public int getLongest(String[] str, int n) {
        if(n == 0) return 0;
        Arrays.sort(str);
        int maxLen = -1;
        //判断每一个字符
        for(int i = 0; i < n; i++) {
            if(getLongestCore(str, str[i], n, i, 0)) maxLen = Math.max(maxLen, str[i].length());
        }
        return maxLen;
    }
    private boolean getLongestCore(String[] str, String s, int n, int strIdx, int start) {
        if(start >= n) return true;
        for(int i = 0; i < strIdx; i++) {
            //如果该字符串头部为前面的某个字符串，则判断该字符串剩余的部分。（有点类似先序的DFS哈）
            if(s.indexOf(str[i]) == 0) {
                return getLongestCore(str, s, n, strIdx, start + str[i].length());
            }
        }
        //尝试了前面所有的可能，都没有匹配，则返回false，表示不能被匹配。
        return false;
    }
}

import java.util.*;

public class LongestString {
    public int getLongest(String[] str, int n) {
        if (str == null || str.length == 0) {
            return 0;
        }
        Arrays.sort(str, new Comparator<String>() {
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });
        int res=0;
        HashSet<String> hs=new HashSet<String>();
        for(String s:str){
            if(fun(hs,s))
                res=s.length();
            hs.add(s);
        }
        return res;
    }
    public boolean fun(HashSet<String> hs,String s){
        if(hs.contains(s))
            return true;
        for(int i=1;i<s.length();i++){
            if(hs.contains(s.substring(0,i))&&fun(hs,s.substring(i,s.length())))
                return true;
        }
        return false;
    }
}