【出自MGYD面试题】
难度系数：★★★★ 被考察系数：★★★☆☆
题目描述：
给定一个字符串数组，找出数组中最长的字符串，使其能由数组中其他的字符串组成。例如给定字符串数组{“test”，“tester”，“testertest”，“testing”，“apple”，“seattle”，“banana”，“batting”，“ngcat”，“batti”，“bat”，“testingtester”，“testbattingcat”}。满足题目要求的字符串为“testbattingcat”，因为这个字符串可以由数组中的字符串“test”、“batti”和“ngcat”组成。
分析与解答：
既然题目要求找最长的字符串，那么可以采用贪心法，首先对字符串由大到小进行排序，从最长的字符串开始查找，如果能由其他字符串组成，就是满足题目要求的字符串。接下来就需要考虑如何判断一个字符串能否由数组中其他的字符串组成，主要的思路是：找出字符串的所有可能的前缀，判断这个前缀是否在字符数组中，如果在，则用相同的方法递归地判断除去前缀后的子串是否能由数组中其他的子串组成。
以题目中给的例子为例，首先对数组进行排序，排序后的结果为{“testbattingcat”，“testingtester”，“testertest”，“testing”，“seattle”，“batting”，“tester”，“banana”，“apple”，“ngcat”，“batti”，“test”，“bat”}。首先取“testbattingcat”进行判断，具体步骤如下：
（1）分别取它的前缀“t”、“te”和“tes”都不在字符数组中，“test”在字符数组中。
（2）接着用相同的方法递归地判断剩余的子串“battingcat”，同理，“b”、“ba”都不在字符数组中，“bat”在字符数组中。(www.xing528.com)
（3）然后判断“tingcat”，通过判断发现“tingcat”不能由字符数组中其他字符组成。因此，回到上一个递归调用的子串接着取字符串的前缀进行判断。
（4）回到上一个递归调用，待判断的字符串为“battingcat”，当前比较到的前缀为“bat”，接着取其他可能的前缀“batt”、“battt”都不在字符数组中，“battti”在字符数组中。接着判断剩余子串“ngcat”。
（5）通过比较发现“ngcat”在字符数组中。因此，能由其他字符组成的最长字符串为“testbattingcat”。
实现代码如下：
程序的运行结果如下：
最长的字符串为：testbattingcat
算法性能分析：
排序的时间复杂度为O（nlog2n），假设单词的长度为m，那么有m种前缀，判断一个单词是否在数组中的时间复杂度为O（mn），由于总共有n个字符串，因此，判断所需的时间复杂度为O（m*n^2）。因此，总的时间复杂度为O（nlog2nm*n^2）。当n比较大的时候，时间复杂度为O（n^2）。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
