Cracking the coding interview--Q20.7

March 4, 2013
作者:Hawstein
出处:http://hawstein.com/posts/20.7.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Write a program to find the longest word made of other words.

译文:

写一个程序,找到由其它单词组成的最长单词。

解答

我们从例子着手开始分析问题。假如我们有一个单词数组,如下:

string arr[] = {"test", "tester", "testertest", "testing", 
			"apple", "seattle", "banana",  "batting", "ngcat", 
			"batti","bat", "testingtester", "testbattingcat"};

哪一个是题目要求的最长单词?这时候假如你有另一个“我”能跳出来, 观察自己的思考过程。你就会发现自己是怎么去解这个问题的, 然后只需要把你的思考过程变成算法,写成代码就OK了。

题目说要找最长单词,所以你的眼睛自然会去寻找那些长单词,至少你不会从bat 开始找起,对吧。找到最长的单词是testbattingcat, 下一步去看它是否可以由其它单词组成。我们发现test是testbattingcat的一部分, bat也是它的一部分,然后呢?剩下的tingcat不能由其它单词构成。不过, 我们可以用test,batti,ngcat来组成它。所以, 它就是我们要找的可以由其它单词组成的最长单词。

把上面的思考过程转换成算法,可以描述如下:

  1. 按单词的长度从大到小排序。(先寻找最长的单词)

  2. 不断地取单词的前缀s,当s存在于单词数组中,递归调用该函数, 判断剩余串是否可以由其它单词组成。如果可以,返回true。

对于上面的例子testbattingcat,我们通过不断取前缀:t不在数组中,te不在数组中, tes不在数组中,test在数组中;递归调用去处理剩余串battingcat,b不在数组中, ba不在数组中,bat在数组中;递归调用去处理剩余串tingcat, 发现它所有的前缀都不存在于数组中,退递归来到处理battingcat那一层。 接着上次的bat继续处理:batt不在数组中,batti在数组中;递归调用去处理剩余串 ngcat,n,ng,ngc,ngca都不在数组中,ngcat存在数组中。递归调用处理剩余串, 发现剩余串为空,返回真。

代码如下:

#include <iostream>
#include <algorithm>
#include "hash.h"
using namespace std;

Hash hash;

inline bool cmp(string s1, string s2){//按长度从大到小排
    return s2.length() < s1.length();
}

bool MakeOfWords(string word, int length){
    //cout<<"curr: "<<word<<endl;
    int len = word.length();
    //cout<<"len:"<<len<<endl;
    if(len == 0) return true;

    for(int i=1; i<=len; ++i){
        if(i == length) return false;//取到原始串,即自身
        string str = word.substr(0, i);
        //cout<<str<<endl;
        if(hash.find((char*)&str[0])){
            if(MakeOfWords(word.substr(i), length))
                return true;
        }
    }
    return false;
}

void PrintLongestWord(string word[], int n){
    for(int i=0; i<n; ++i)
        hash.insert((char*)&word[i][0]);
    sort(word, word+n, cmp);

    for(int i=0; i<n; ++i){
        if(MakeOfWords(word[i], word[i].length())){
            cout<<"Longest Word: "<<word[i]<<endl;
            return;
        }
    }
}

int main(){
    string arr[] = {"test", "tester", "testertest", "testing", 
				"apple", "seattle", "banana",  "batting", "ngcat", 
                "batti","bat", "testingtester", "testbattingcat"};
    int len = 13;
    PrintLongestWord(arr, len);
    return 0;
}

上述代码将单词存放在哈希表中,以得到O(1)的查找时间。排序需要用O(nlogn)的时间, 判断某个单词是否可以由其它单词组成平均需要O(d)的时间(d为单词长度), 总共有n个单词,需要O(nd)的时间。所以时间复杂度为:O(nlogn + nd)。 n比较小时,时间复杂度可以认为是O(nd);n比较大时,时间复杂度可以认为是O(nlogn)。

注意上述代码中有一句:

 if(i == length) return false;//取到原始串,即自身

意思是当我们取一个单词前缀,最后取到整个单词时, 这种情况就认为是没有其它单词可以组成它。如果不要这一句, 那么你在哈希表中总是能查找到和它自身相等的串(就是它自己),从而返回true。 而这明显不是我们想要的。我们要的是其它单词来组成它,不包括它自己。

这样一来,又引出一个问题,如果单词中就是存在两个相同的单词。 比如一个单词数组中最长的单词是abcdefg,并且存在2个,而它又不能被更小的单词组成, 那么我们可以认为这个abcdefg是由另一个abcdefg组成的吗? 关于这一点,你可以和面试官进行讨论。(上述代码认为是不能的。)

由于使用哈希表会占用较多空间,一种不使用额外空间的算法是直接在单词数组中查找, 由于单词数组已经按长度从大小到排,因此单次查找时间为O(n)。一共有n个单词, 平均长度为d,所以总共需要的时间为O(nd*n)=O(dn^2 )。 如果我们再开一个数组来保存所有单词,并将它按字典序排序, 那么我们可以使用二分查找,单次查找时间变为O(logn),总共需要O(dnlogn)。

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview