最长合成字符串_

小白菜这名字居然有人取了

先按字符串长度排个序哦，然后从长度最长的开始判断是否是由其他的合成的。
每次都从字符串的前端开始切，递归地判断~
如果觉得写得还行的就给点个赞吧，这么久了只有自己给自己点的两个赞好孤独啊>_<
class LongestString {
public:
    static bool cmp(string a, string b)
    {
        return a.length() > b.length();
    }
    int getLongest(vector<string> str, int n) {
        // write code here
        sort(str.begin(), str.end(), cmp);
        int max = 0;
        for(int i = 0; i <= n; i++)
        {
            if(Other(str, str[i], i, n))
                return str[i].length();
        }
        return -1;
    }
    bool Other(vector<string> str, string s, int index, int n)
    {
        if(s.length() == 0)
            return true;
        for(int i = 0; i < n; i++)
        {
            if(i != index)
            {
                if(s.find(str[i]) == 0)
                {
                    if(Other(str, s.substr(str[i].length()), index, n))
                        return true;
                }
            }
        }
        return false;
    }
};

发表于 2016-05-20 23:42:10 回复(1)

NowaCoder

我贴一下我的代码，不知道为什么要设置true或者false,感觉完全没有意义啊，好多人都设置，
我觉得是根本没必要的，这道题用HashMap结构是降低containsKey()的复杂度为O（1），如果包含
可以直接返回true,没必要对当前boolean进行设置，也就是说boolean是没有用到的，如有不妥
欢迎指正
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>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.length() - o1.length();
            }
        });
        Map<String, Boolean> map = new HashMap<>();
        for (String key : str) {
            map.put(key,null);
        } 
        for (String string : str) {
            if (canBuildWord(string, true, map)) {
                return string.length();
            }
        }
        return 0;
    }
 
    private boolean canBuildWord(String str, boolean isOriginal, Map<String, Boolean> map) {
        if (map.containsKey(str)&&!isOriginal) {
            return true;
        }
        for (int i = 1; i < str.length(); i++) {
            String left = str.substring(0, i);
            String right = str.substring(i);
            if (map.containsKey(left)&&canBuildWord(right, false, map)) {
                return true;
            }
        }
        return false;
    }
 
}

发表于 2017-02-10 16:06:01 回复(5)

跳刀躲梅肯塔下意识粉

这题简单一点,就是判断一个单词是否能由其他的单词组合而成,不过问题还是有点复杂,那就先切分成一个单词能否由另外两个单词构成:

首先利用一个map记录下来所有其他的单词,然后通过下面的伪代码判断:

bool canBuild(string& s,map<string,boo> & record){

for(int i=0;i<len;i++){

if(record.containKey(s[0-i])&&record.containKey[s[i-len]]) return true;//left,right是否都出现

}

return false;

}

就是通过一个map,判断这个string的左边是否出现,右边是否出现.

那么扩展到由多个单词组成:

这里可以使用递归,只判断当前的左边子串,右边子串通过递归来判断:

代码:

 bool canBuild(string & s,bool started, map<string, bool> &record){
  if (!started&&record.find(s) != record.end()) return record[s];
//因为map当中记录了其他元素,因此需要通过started来区分是
//子串还是原本数组当中的字符串.
  for (int i = 1; i < s.size(); i++){
   string left = s.substr(0, i);
   string right = s.substr(i, s.size() - i + 1);
   if (record.find(left) != record.end()&&record[left] 
&& canBuild(right,false,record)) return true;
  }
  record[s] = false;
//通过记录不成功,将本次结果利用到下次判断当中.不需要重复计算
  return false;
 }

代码:

bool myfunction(string i, string j) { 
return (i.length() < j.length()); 
}
class LongestString {
public:
 int getLongest(vector<string> str, int n) {
  // write code here
  map<string, bool> record;
  for (string s : str) record[s] = true;
  sort(str.begin(), str.end(), myfunction);
  for (int i = n - 1; i >= 0; i--){
   if (canBuild(str[i], true, record)) 
        return str[i].length();
  }
  return -1;
 }
 
 bool canBuild(string & s,bool started, map<string, bool> &record){
  if (!started&&record.find(s) != record.end()) return record[s];
  for (int i = 1; i < s.size(); i++){
   string left = s.substr(0, i);
   string right = s.substr(i, s.size() - i + 1);
   if (record.find(left) != record.end()&&record[left]
 && canBuild(right,false,record)) return true;
  }
  record[s] = false;
  return false;
 }
};

编辑于 2015-09-09 14:50:52 回复(0)

revivedSuN

题目意思是说数组中的某个串，能否由数组中的串拼接而成。

例如["a","b","c","ab","bc","abc"]

abc可以由 a,b,c或a,bc构成

ab 可以由 b,c构成。

bc b,c构成

最终返回可以由其它子串拼接而成的串中，长度最长的串。

abc和ab都可以由其它的子串拼接而成，然后abc长度为3所以结果是3。

一个串可以分解为它的前缀和后缀组成。前缀和后缀同理可以这样分解，然后检查即可。

string strs[] = {"a","b","c","abc"}; 结果返回3。

编辑于 2015-09-01 14:47:11 回复(0)

已注销

class LongestString {
public:
    //排序函数的比较器
    static bool comp(const string& a,const string& b)
    {
        return a.length()>b.length();
    }
    //主体函数
    int getLongest(vector<string> str, int n) {
        // write code here
        sort(str.begin(),str.end(),comp);//按从长到短的单词进行排序
        map<string,bool> mymap;
        for(auto s:str)  
            mymap[s]=true;
        //循环判断每个单词能否由其他单词组成
        for(unsigned int i=0;i<str.size();i++)
        {
            if(canBuild(str[i],true,mymap))//初始传入一个true，如果这个单词不能构成，下面会优化成false;
                return str[i].length();
        }
        return 0; 
    }
    //判断函数，关键代码
    bool canBuild(string& str,bool started ,map<string,bool>& mymap)
    {
        if(!started && mymap.count(str)) return mymap[str];//核心代码，如果是false，就直接检查返回了
        int len=str.length();
        for(int i=1;i<len;i++)
        {
            string left=str.substr(0,i);//下标0开始，长度为i个
            string right=str.substr(i,len-i+1);//长度len-i+1，不包含最后一个
            if(mymap[left]&&canBuild(right,false, mymap))
                    return true;
        }
        mymap[str]=false;
        return false;
    }
};

//第二种思路
class LongestString {
public:
    //排序函数的比较器
    static bool comp(const string& a,const string& b)
    {
        return a.length()>b.length();
    }
    //主体函数
    int getLongest(vector<string> str, int n) {
        // write code here
        sort(str.begin(),str.end(),comp);//按从长到短的单词进行排序
        map<string,bool> mymap;
        for(auto s:str)  
            mymap[s]=true;
        //循环判断每个单词能否由其他单词组成
        for(unsigned int i=0;i<str.size();i++)
        {
           int len=str[i].length();
           string temp=str[i];
           for(int i=1;i<len;i++)
            {
               string left=temp.substr(0,i);//下标0开始，长度为i个
               string right=temp.substr(i,len-i+1);//长度len-i+1，不包含最后一个
               if(mymap[left]&&canBuild(right,mymap))
                    return temp.length();
           }
        }
        return 0; 
    }
    //判断函数，关键代码
    bool canBuild(string& str,map<string,bool>& mymap)
    {
        if(mymap[str]) 
            return true;//核心代码，如果是false，就直接检查返回了
        int len=str.length();
        for(int i=1;i<len;i++)
        {
            string left=str.substr(0,i);//下标0开始，长度为i个
            string right=str.substr(i,len-i+1);//长度len-i+1，不包含最后一个
            if(mymap[left]&&canBuild(right,mymap))
                    return true;
        }
        //mymap[str]=false;
        return false;
    }
};

编辑于 2016-08-19 22:08:43 回复(0)

Aurora1

class LongestString:
    def getLongest(self, s, n):
        m = {k: True for k in s}
        s.sort(key=lambda k: len(k), reverse=True)
        for i in range(n):
            if self.f(s[i], m, True):
                return len(s[i])

    def f(self, k, m, b):
        if not b and k in m:
            return m[k]
        for i in range(1, len(k)):
            if self.f(k[0:i], m, False) and self.f(k[i:], m, False):
                return True
        m[k] = False
        return False

发表于 2017-03-19 13:20:05 回复(0)

C/C++

J.Fan

//主要是切分字符串
class LongestString {
public:
    bool dfs(vector<string>& str,int& targe_ind,int ind)
    {
        if(ind >= str[targe_ind].size())
            return true;
        for(int i=0;i<str.size();++i)
        {
            if(i == targe_ind)
            {
                continue;
            }
            if(str[targe_ind].substr(ind,str[i].size()) == str[i])
            {
                if(dfs(str,targe_ind,ind+str[i].size()))
                    return true;
            }
        }
        return false;
    }
    int getLongest(vector<string> str, int n) {
        // write code here
        if(n < 1)
            return 0;
        sort(str.begin(),str.end(),[](const string& s1,const string& s2){
            if(s1.size() == s2.size())
                return s1 < s2;
            return s1.size() > s2.size();
        });
        for(int i=0;i<str.size();++i)
        {
            if(dfs(str,i,0))
                return str[i].size();
        }
        return 0;
    }
};

发表于 2020-07-15 21:51:50 回复(0)

C/C++

nbgao

class LongestString {
public:     static bool cmp(string a, string b){         return a.size() < b.size();     }
    int getLongest(vector<string> str, int n) {
        sort(str.begin(), str.end(), cmp);
        for(int i=n-1;i>=0;i--){
            string t = str[i];
            int x;
            for(int j=i-1;j>=0;j--)                 while((x=t.find(str[j])) != -1)                     t.erase(x, str[j].size());             if(t.empty())                 return str[i].size();         }         return -1;
    }
};

发表于 2019-03-12 13:23:33 回复(0)

C/C++

Ga_li_dun_farming_guy

// 个人感觉不需要排序，不过排序会好一点，从头到尾，可以少遍历一些元素。
// 个人不太明白为什么大家不拆左边的字符串，于是还是拆了一下。
// 其中compare 函数parameters list ： 存有所有字符串的map，当前字符串，是否是自己本身
// 这三个参数
// 代码如下：
class LongestString {
public:
    bool compare(map<string,int> &stringMap, string item, bool selfString) {
        if (stringMap[item] == 1 && !selfString) return true;
        for (int i = 1; i < item.size() ; i++) {
            if(compare(stringMap, item.substr(0,i),false) && 
                compare(stringMap, item.substr(i),false))
                return true;
        }
        return false;
    }
    int getLongest(vector<string> str, int n) {
        // write code here
        int maxRe = 0;
        map<string,int> stringMap;
        for (int i = 0 ; i != n ; i++)
            stringMap[str[i]] = 1;
        for (int i = 0 ; i != n ; i ++) {
            if(compare(stringMap,str[i],true)) {
                maxRe = maxRe > str[i].length()? maxRe : str[i].length();
            }
        }
        return maxRe;
    }
};

发表于 2019-02-11 14:05:41 回复(0)

Java

BrownLincoln

//思路:先将字符串数组按照字母序排序。然后，采用递归的方式来进行判断。
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;
    }
}

发表于 2017-08-24 14:12:14 回复(1)

Cavs

从最长的字符串开始判断是否由其他字符串构成，这里注意排除该字符串自身。
#include <unordered_set>
class LongestString {
private:
	unordered_set<string> hs;
	bool canFound(string& s, int pos)
	{
		if (pos == s.size()) return true;
		int n = s.size();
		if (pos == 0) --n;
		for (int i = pos; i < n; ++i)
		{
			if (hs.find(s.substr(pos, i - pos + 1)) != hs.end()
				&& canFound(s, i + 1))
				return true;
		}
		return false;
	}
public:
	int getLongest(vector<string> str, int n)
	{
		hs.insert(str.begin(), str.end());
		sort(str.begin(), str.end(),
			[](const string& s1, const string& s2)
			{
			return s1.size() > s2.size();
			});
		for (auto& s : str)
		{
			if (canFound(s, 0)) return s.size();
		}

		return str[n - 1].size();
	}
};

发表于 2017-07-02 16:06:35 回复(0)

gloomy

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>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.length() - o1.length();
            }
        });
        Map<String, Boolean> map = new HashMap<>();
        for (String key : str) {
            map.put(key, true);
        }
        for (String string : str) {
            if (canBuildWord(string, true, map)) {
                return string.length();
            }
        }
        return 0;
    }

    private boolean canBuildWord(String str, boolean isOriginal, Map<String, Boolean> map) {
        if (map.containsKey(str) && !isOriginal) {
            return map.get(str);
        }
        for (int i = 1; i < str.length(); i++) {
            String left = str.substring(0, i);
            String right = str.substring(i);
            if (map.containsKey(left) && map.get(left) && canBuildWord(right, false, map)) {
                return true;
            }
        }
        map.put(str, false);
        return false;
    }

}

发表于 2016-09-07 15:41:38 回复(0)

幻之飞雪

public class LongestString {
	class LenCmp<String> implements Comparator<String>
	{
	    @Override
	    public int compare(String o1, String o2)
	    {
	        return o1.toString().length()-o2.toString().length();
	    }
	         
	}
	public  int getLongest(String[] str, int n) {
	// 找到最长的字符串
	    Arrays.sort(str,new LenCmp());
	    HashMap<String,Boolean> map=new HashMap<String,Boolean>();
	    for(String s:str)
	    {
	        map.put(s,true);//map作为一个查找的工具
	    }
	    //从最长的一个开始查找
	    for(int i=str.length-1;i>=0;i--)
	    {
	        //对于每一个str拆分成两个  找出所有可能拆成2个的所有情况
	        //第一个直接去 map找 第一个递归的找  这样可以覆盖所有的情况
			for(int j=1;j<str[i].length();j++)
	        {
	            String str1=str[i].substring(0, j);
	            String str2=str[i].substring(j,str[i].length());
	            if(map.containsKey(str1)&&conBuild(map,str2))
	                return str[i].length();
	        }
	    }
	        
	    return 0;
	}
	 
	private boolean conBuild(HashMap<java.lang.String, Boolean> map, java.lang.String str)
	{
	    if(map.containsKey(str))
	        return true;
	    for(int j=1;j<str.length();j++)
	    {
	        String str1=str.substring(0, j);
	        String str2=str.substring(j,str.length());
	        if(map.containsKey(str1)&&conBuild(map,str2))
	            return true;
	    }
	    return false;
	}
}

参考sunny_wf

发表于 2016-06-14 12:13:30 回复(0)

double_xuan

class LongestString:
    def getLongest(self, s, n):
        s.sort(key=len)
        s.reverse()
        for i in range(n):
            data = s[i]
            for j in range(i+1,n,1):
                if s[j] in s[i]:
                    s[i] = s[i].replace(s[j],'')
                    j = j+1
            if s[i] == '':
                break
        return len(data)

分享一个逻辑简单一点的，没有用递归：

1.按长度从大到小排序

2.对每个串，循环判断看后面是否有串是其组成成分。如果有，去掉该成分串，并急需循环；如果没有，判断下一个

3.一旦该串内容全部被清空，返回该串的长度。

发表于 2018-04-20 09:13:45 回复(0)

小哇公子

public int getLongest(string[] str, int n)//不考虑数据空数组的情况
{
// write code here
if(n==1)
{
return (int)str[0].Length;
}
else
{
if(str[n-1].Length>getLongest(str,n-1))
return (int)str[n-1].Length;
else
return getLongest(str,n-1);
}
}

发表于 2022-04-20 12:46:38 回复(0)

cc菜

publicintgetLongest(String[] str, intn) {

if(str.length <3) {

return0;

}

List<String> list = newArrayList<String>();

for(inti =0; i < str.length ; i++) {

String target = str[i];

String[] newArray = getNewArray(str, i);

process(newArray,"",target,list);

}

list.sort((a,b)->{

returnb.length()-a.length();

});

returnlist.get(0).length();

}

public voidprocess(String[] arr ,String cur , String target , List<String> list) {

if(target == ""|| target.length()==0) {

if(!list.contains(cur)) {

list.add(cur);

}

return;

}

for(inti = 0; i<arr.length && isOk(arr,target) ; i++ ) {

String str = arr[i];

if(target.indexOf(str) == 0){

String rest = target.substring(str.length());

process(arr,cur+str,rest,list);

}

public booleanisOk(String[] arr , String target){

for(String str : arr) {

if(target.indexOf(str) == 0) {

returntrue;

}

returnfalse;

}

public String[] getNewArray(String[] str, intindex){

String[] help = newString[str.length-1];

inthelpIndex = 0;

for(inti = 0; i < str.length ; i++ ) {

if(index != i ){

help[helpIndex++] =str[i];

}

returnhelp;

}

发表于 2022-03-15 00:30:42 回复(0)

谭雷

兴业数金编程题，花了很多时间（手动滑稽）

原题是求最长单词，该单词能被数组内其他单词组成，如果有同样长，取字典顺序最小的

public String longestWord(String[] words) {
        Arrays.sort(words, (o1, o2) -> o2.length() - o1.length());
        // write code here
        String result = "";
        int maxLength = 0;
        for (int i = 0; i < words.length; i++) {
            String wordLong = words[i];
            if (wordLong.trim().length() == 0) {
                continue;
            }
            for (int j = i + 1; j < words.length; j++) {
                String wordShort = words[j];
                wordLong = wordLong.replaceAll(wordShort, "");
                if (wordLong.length() == 0) {
                    //bingo
                    //字典序
                    if (words[i].length() > maxLength) {
                        maxLength = words[i].length();
                        result = words[i];
                    } else if (words[i].length() == maxLength) {
                        if (words[i].charAt(0) < result.charAt(0)) {
                            result = words[i];
                        }
                    }
                    break;
                }
            }
        }
        return result;
    }

发表于 2022-02-08 00:27:42 回复(0)

TankWitch

class LongestString {
public:
    int getLongest(vector<string> str, int n) {
        // write code here
        multiset<string> ss;
        int maxLen = -1;
        for (int i = 0; i < n; ++i) {
            ss.insert(str[i]);
        }
        for (int i = 0; i < n; ++i) {
            int len = -1;
            if (ss.count(str[i]) > 1) {
                len = str[i].size();
            } else {
                len = isContain(ss, str[i], str[i].size() );
            }
            maxLen = max(maxLen, len);
        }
        return maxLen;
    }
private:
    int isContain(multiset<string> &ss, string &str, size_t size) {
        for (size_t i = 1; i < size; ++i) {
            string left = str.substr(0, i); // {a}bc
            string right = str.substr(i, size - i); // ab{c}
            if (ss.count(left) && ss.count(right)) {
                return str.size();
            }
        }
        return -1;
    }
};

发表于 2020-08-02 10:51:07 回复(0)

Java

野生小硕

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

思想：

如果一个字符串是由数组中其他字符串组成，那么该字符串中的每个字符出现的次数是大于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;
              }
          }
      }
  }

发表于 2020-07-24 15:57:52 回复(0)

包子冲汤胡辣汤

class LongestString {
public:
    static int cmp(string s1,string s2){
        if(s1.size()!=s2.size())
            return s1.size()>s2.size();
    }
    bool getlongest(vector<string> str,string s,int index,int n){
        if(s.size()==0){
            return true;
        }
        for(int i=index+1;i<n;++i){
            if(s.find(str[i])==0){
                if(getlongest(str,s.substr(str[i].size()),index,n))
                {
                    return true;
                }
            }
        }
        return false;
    }
    int getLongest(vector<string> str, int n) {
        // write code here
        int i;
        sort(str.begin(),str.end(),cmp);
        for(i=0;i<n;++i){
            if(getlongest(str,str[i],i,n))
                return str[i].size();
        }
        if(i==n)
            return 0;
    }
};

发表于 2020-04-03 15:30:11 回复(0)

最长合成字符串

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

思想：

基于以上想法：

问题信息

热门推荐

通过挑战的用户

相关试题