给定一个string数组str及其大小n。请编写一段代码找出该数组中最长的那个字符串,且要求该字符串能由数组中其他的字符串组成(使用的字符串可重复)。请返回满足要求的最长字符串的长度,保证题意所述的最长单词存在。
测试样例:
["a","b","c","ab","bc","abc"],6
返回:3
先按字符串长度排个序哦,然后从长度最长的开始判断是否是由其他的合成的。 每次都从字符串的前端开始切,递归地判断~ 如果觉得写得还行的就给点个赞吧,这么久了只有自己给自己点的两个赞好孤独啊>_< 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; } };
我贴一下我的代码,不知道为什么要设置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; } }
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; } }; |
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; } };
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)
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
//主要是切分字符串 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; } };
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; } };
// 个人感觉不需要排序,不过排序会好一点,从头到尾,可以少遍历一些元素。 // 个人不太明白为什么大家不拆左边的字符串,于是还是拆了一下。 // 其中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; } };
//思路:先将字符串数组按照字母序排序。然后,采用递归的方式来进行判断。 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; } }
从最长的字符串开始判断是否由其他字符串构成,这里注意排除该字符串自身。 #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(); } };
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; } }
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; } }
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; }
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; } };
如果一个字符串是由数组中其他字符串组成,那么该字符串中的每个字符出现的次数是大于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; } } } }
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; } };