document.write('既然题目要求找最长的字符串，那么可以采用贪心法，首先对字符串由大到小进行排序，从最长的字符串开始查找，如果能由其他字符串组成，那么就
是满足题目要求的字符串。接下来就需要考虑如何判断一个字符串能否由数组中其他的字符串组成，主要的思路为：找出字符串的所有可能的前缀，判
断这个前缀是否在字符数组中，如果在，那么用相同的方法递归地判断除去前缀后的子串是否能由数组中其他的子串组成。
以题目中给的例子为例，首先对数组进行排序，排序后的结果为：
[“testbattingcat”，“testingtester”，“testertest”，“testing”，“seattle”，“batting”，“tester”，“banana”，“apple”，“ngca
首先取“testbattingcat”进行判断，具体步骤如下：
(1)分别取它的前缀“t”，“te”，“tes”都不在字符数组中，“test”在字符数组中。
(2)接着用相同的方法递归地判断剩余的子串“battingcat”，同理，“b”，“ba”都不在字符数组中，“bat”在字符数组中。
(3)然后判断“tingcat”，通过判断发现“tingcat”不能由字符数组中其他字符组成。因此，回到上一个递归调用的子串接着取字符串的前缀进行判
断。
(4)回到上一个递归调用，待判断的字符串为“battingcat”，当前比较到的前缀为“bat”，接着取其他可能的前缀“batt”，“battt”都不在字符
数组中，“battti”在字符数组中。接着判断剩余子串“ngcat”。
(5)通过比较发现“ngcat”在字符数组中。因此，能由其他字符组成的最长字符串为“testbattingcat”。
实现代码如下：
class LongestWord:
#方法功能: 判断字符串strs是否在字符串数组中
def find(self,strArray,strs):
i=0
while i＜len(strArray):
if strs==strArray[i]:
return True
i+=1
return False
"""
方法功能: 判断字符串word是否能由数组strrArray中的其他单词组成
参数: word为待判断的后缀子串, length待判断字符串的长度
"""
def isContain(self,strArray,word,length):
lens=len(word)
#递归的结束条件, 当字符串长度为0时, 说明字符串已经遍历完了
if lens==0:
return True
#循环取字符串的所有前缀
i=1
while i=lens:
#取到的子串为自己
if i==length:
return False
strs=word[0:i]
if selffind(strArray,strs):
#查找完字符串的前缀后, 递归判断后面的子串能否由其他单词组成
if self.isContain(strArray, word[i:], length):
return True
i+=1
return False
#方法功能: 找出能由数组中其他字符串组成的最长字符串
def getLogestStr(self,strArray):
#对字符串由大到小排序
strArray=sorted(strArray,key=len,reverse=True)
print strArray
#贪心地从最长的字符串开始判断
i=0
while i＜len(strArray):
if self.isContain(strArray, strArray[i],len(strArray[i])):
return strArray[i]
i+=1
#如果没找到, 那么返回空串
return None
if __name__=="__main__":
strArray=["test\', "tester", "testertest", "testing", "apple", "seattle", "banana", "batting","ngcat", "batti", "bat", "testingtester",
"testbattingcat"]
lw=LongestWord()
logestStr=lw.getLogestStr(strArray)
if logestStr!=None:
print "最长的字符串为: "+logestStr
else:
print "不存在这样的字符串"
程序的运行结果为：
最长的字符串为：testbattingcat
算法性能分析：
排序的时间复杂度为O(nlogn)，假设单词的长度为m，那么有m种前缀，判断一个单词是否在数组中的时间复杂度为O(mn)，由于总共有n个字符
串，因此，判断所需的时间复杂度为O(m*n2)。因此，总的时间复杂度为O(nlogn+m*n2)。当n比较大的时候，时间复杂度为O(n2)。
');