Edit Ladders

Edit Ladders

---

Time Limit:5s	Memory limit:32M
Accepted Submit:32	Total Submit:155

---

An edit step is a transformation from one word x to another word y such that x and y are words in the dictionary, and x can be transformed to y by adding, deleting, or changing one letter. So the transformation from dig to dog or from dog to do are both edit steps. An edit step ladder is a lexicographically ordered sequence of words w₁, w₂, ... w_n such that the transformation from w_i to w_i+1 is an edit step for all i from 1 to n-1.

For a given dictionary, you are to compute the length of the longest edit step ladder. The input to your program consists of the dictionary - a set of lower case words in lexicographic order - one per line. No word exceeds 16 letters and there are no more than 25000 words in the dictionary. The output consists of a single integer, the number of words in the longest edit step ladder.

Sample Input

cat
dig
dog
fig
fin
fine
fog
log
wine

Output for Sample Input

5

#include<stdio.h>
#include<string.h>

#define MAX_VAL(x, y) ((x) > (y) ? (x) : (y))

struct words
{
    int len;
    struct words *next[26];
};

struct words *root;
struct words word[250000];
int index0;

int find_len(struct words *root, char *p, int del)
{
    int i, maxv, a;
    int next_list;

    maxv = a = 0;
    next_list = *p - 'a';

    if (del == 1)
    {
        if (*p == '\0')
            return root->len;
        else if (root->next[next_list] == NULL)
            return 0;
        else
            return find_len(root->next[next_list], p + 1, del);
    }

    for (i = 0; i < 26; ++i)
    {
        if (root->next[i] != NULL)
        {
            a = find_len(root->next[i], p, 1);
            maxv = MAX_VAL(maxv, a);

            if (*p != '\0')
            {
                a = find_len(root->next[i], p + 1, 1);
                maxv = MAX_VAL(maxv, a);
            }
        }
    }

    if (*p == '\0')
        return MAX_VAL(maxv, root->len);

    if (root->next[next_list] != NULL)
    {
        a = find_len(root->next[next_list], p + 1, del);
        maxv = MAX_VAL(maxv, a);
    }

    ++p;
    next_list = *p - 'a';
    if (*p == '\0')
        return MAX_VAL(maxv, root->len);
    if (root->next[next_list] != NULL)
    {
        a = find_len(root->next[next_list], p + 1, 1);
        maxv = MAX_VAL(maxv, a);
    }

    return maxv;
}

struct words * insert(struct words *root, char *p, int len)
{
    int i;
    if (root == NULL)
    {
        for (i = 0; i < 26; ++i)
            word[index0].next[i] = NULL;
        word[index0].len = 0;
        root = &word[index0];
        ++index0;
    }

    if (*p == NULL)
        root->len = MAX_VAL(len, root->len);
    else
        root->next[*p - 'a'] = insert(root->next[*p - 'a'], p + 1, len);

    return root;
}

int main()
{
    int i;
    int len;
    int result;
    char str[20];

    result = 0;
    index0 = 0;
    for (i = 0; i < 26; ++i)
        word[index0].next[i] = NULL;
    word[index0].len = 0;
    root = &word[index0];
    ++index0;
    while (gets(str))
    {
        len = find_len(root, str, 0);
        ++len;
        root = insert(root, str, len);
        result = MAX_VAL(result, len);
    }
    printf("%d\n", result);
    
    return 0;
}