UVA 10029 Edit Step Ladders(dp)

Problem C: Edit Step Ladders

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 w1, w2, ... wn such that the transformation from wi to wi+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.

Input

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.

Output

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

Sample Output

5

题意：给定一个字典，如果经过删除，添加或替换能转换成另一个单词，则这两个单词为阶梯变化 ， 求出最长阶梯变化的字典。

思路：dp。lis，用n^2 超时了。。。然后没想明白看题解，发现有n(logn)方法。

把每个单词可以变换的情况全部弄出来，然后在前面进行2分查找，由于序列本身是字典序所以可行 。这样就能过了

代码：

#include <stdio.h>
#include <string.h>
int max(int a, int b) {return a > b ? a : b;}
int min(int a, int b) {return a < b ? a : b;}
const int N = 25555, M = 20;
char word[N][M], str[M];
int n, i, j, k, l, dp[25555], ans;

void change(char *word, char *str, char c, int wei) {
    int i;
    for (i = 0; word[i]; i ++)
        str[i] = word[i];
    str[wei] = c;
    str[i] = '\0';

}

void del(char *word, char *str, int wei) {
    int i;
    for (i = 0; i < wei; i ++)
        str[i] = word[i];
    for (i = wei + 1; word[i]; i ++)
        str[i - 1] = word[i];
    str[i - 1] = '\0';
}

void add(char *word, char *str, char c, int wei) {
    int i;
    for (i = 0; i < wei; i ++)
        str[i] = word[i];
    str[wei] = c;
    for (i = wei; word[i]; i ++)
        str[i + 1] = word[i];
    str[i + 1] = '\0';
}

void tra(char *word, char *str, char c, int wei, int flag) {
    if (flag == 0) change(word, str, c, wei);
    else if (flag == 1) del(word, str, wei);
    else add(word, str, c, wei);
}

int find(char *str, int j) {
    int i = 0;
    j --;
    while (i <= j) {
        int mid = (i + j) / 2;
        if (strcmp(word[mid], str) == 0) {
            return mid;
        }
        else if (strcmp(word[mid], str) < 0) {
            i = mid + 1;
        }
        else
            j = mid - 1;
    }
    return -1;
}

int main() {
    while (gets(word[n])) {
        n ++;
    }
    ans = 0;
    for (i = 0; i < n; i ++) {
        dp[i] = 1;
        for (k = 0; k < 3; k ++) {
            for (j = 0; word[i][j]; j ++) {
                for (l = 0; l < 26; l ++) {
                    tra(word[i], str, 'a' + l, j, k);
                    if (strcmp(word[i], str) < 0) break;
                    int mid = find(str, i);
                    if (mid >= 0) dp[i] = max(dp[i], dp[mid] + 1);
                }
            }
        }
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索word
， int
， dictionary
， char
， str
The
ladders、snakes and ladders、chutes and ladders、climbing ladders、go up the ladders，以便于您获取更多的相关知识。