有一组单词，请编写一个程序，在数组中找出由数组中字符串组成的最长的串A，即A是由其它单词组成的(可重复)最长的单词。 给定一个string数组str，同时给定数组的大小n。请返回最长单词的长度，保证题意所述的最长单词存在。 测试样例： ["a","b","c","ab","bc","abc"],6 返回：3
这题简单一点,就是判断一个单词是否能由其他的单词组合而成,不过问题还是有点复杂,那就先切分成一个单词能否由另外两个单词构成:
首先利用一个map记录下来所有其他的单词,然后通过下面的伪代码判断:
bool canBuild(string& s,map
for(int i=0;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 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 // write code here map 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 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; } };
