微软面试100题(37):重合字符串连接

有n个长为m+1的字符串，如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。

这是一个看着容易做起来难的题。如果真是面试的时候，或许能想到算法，但是要现场写出能run的代码，实在无能为力。。。

1.建立一个struct, 每个串对应一个。value是串的内容。count是它的后面能够链接的字符串的个数。然后一个children数组，存储每个它后面能够连接的字符串的结构体。

2.预处理所有数据，处理每个输入，转成上面定义的结构体，列出每个串后面能与他链接的字符串，以及满足条件个数。为处理方便，让所有结构体连续存储，这样可以简单遍历。

3.可以想象，所有的结构体最后组成了一个图，连通或者不联通。这个问题就转化为求这个图中距离最远的两个点的距离。这里，运用了动态规划的想法，避免了重复对某个点进行尝试。

4. 用一个数组result存储每个串最长能链接的个数。初值为0. 对于一个串str, result[str]就是它能拼接的最大长度。

5. 遍历2中得到的数组。

  a. 对于一个元素elem，如果他的count不为0,那么说明有串能接在他的后面.若没有，那么它后面不能拼接任何串，result[elem] = 1。

  b. 遍历它children，对于其中的一个后缀连接(tailstr)，看result数组中这个tailstr对应的值是否为0

       I.如果不为0,说明后续长度就是result[tailstr],那么当前元素elem和tailstr的拼接的最大长度就是tmp=result[tailstr]+1.直到遍历完成，记录tmp达到的最大值，那么当前元素elem能链接的串最长就是tmp个.写入result数组result[elem] = tmp.

       II.如果为0,说明这个串还没被处理过，那么递归调用b.

6. 必须保证每个串都被处理一遍。完成之后，算法结束。

 

7.为了发现环的问题，还需要引入一个变量，记录递归嵌套的深度，如果深度超过了输入字符串的个数了，那么说明有环，直接返回-1.

7。最后便利result数组，就能得出可能达到的最长的长度。当然，也可以设置一个全局变量记录最大值max，每次往result里面写的时候，和max比较，如果当前写入值更大那么就更新max.这样可以少一次循环。

复杂度分析：

在预处理阶段，对与一个串，显然是要比n次。所以预处理的复杂度为O(n^2);

找出最长路径的算法，每个点如果得出结果了，那么就存入result,下次就不需要再处理了。所以一个点只处理1次。这个复杂度应该是O(n);

因为用c实现，所以没有keyvaluepair之类的数据结构，只能用一个连续数组来存储结构体，这样就导致了没法通过串的值当作key来索引。 因此result用了蹩脚的地址偏移量来获取下标。

/*
 * =====================================================================================
 *
 *       Filename:  strcombine.c
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  10/05/2012 10:30:18 AM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *   Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include    <stdio.h>

#define MAX 1000
#define LEN 3
typedef struct tagword{
    const char *value;
    int count;
    struct tagword*  children[MAX];
} word;

int Size;
int result[MAX]= {0};
word* Base;

char IsMatch(const char* src, const char* pattern){
    int i = 0;
    for(;i<LEN-1;i++){
        if(*(src+i+1) != *(pattern+i)) return 0;
    }
    printf ( "%s matched %s\n", src, pattern );
    return 1;
}

word* prepare(char **input, int size){
    word* head = (word *)malloc(sizeof(word) * size);
    int i = 0;
    for(;i<size;i++){
        head[i].value = input[i];
        head[i].count = 0;
    }
    for(i=0;i<size;i++){
        int m = 0;
        for(;m<size;m++){
            if( m!=i && IsMatch(head[i].value, head[m].value)){
                (head[i].children)[head[i].count++] = &head[m];
            }
        }
    }
    return head;
}
int track(word* head, int dep){
    if(dep > Size) return -1;
    int i = 0;
    dep++;
    int tmp = 0;
    if(result[head-Base] != 0){
        return result[head-Base];
    }
    for(;i < head->count; i++){
        printf ( "tracking child %s\n",(head->children[i])->value );
        int cdep = track(head->children[i], dep);
        if(cdep == -1) return cdep;
        if(tmp < cdep) tmp = cdep;

    }
    tmp++;
    printf ( "%d -> %d \n", head-Base, tmp );
    result[head-Base] = tmp;
    return tmp;

}

/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    char * input[]= {"bcd","cde","def", "abc","deg","egh"};
    Size =  sizeof(input)/(LEN+1);
    word* head  = prepare(input, Size);
    Base = head;
    int i = 0;
    for(;i<Size; i++){
        track(head++,0);
    }
    int max = 0;
    for(i = 0; i<Size; i++){
        max = max>result[i]?max:result[i];
        printf ( "%d \n", result[i] );
    }
    printf ( "max length is %d\n", max );
    return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */