Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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 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.

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

---

雖然這題是要求挑一個最長字典順序，而相鄰兩個單字可以藉由增加，刪除，修改達到。

不可能一個一個去比較，因此要窮舉可以修改成什麼，然後去做查找。


// 使用 map

#include <stdio.h>
#include <string.h>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;

int dp[25005];
map<string, int> R[50];
//adding, deleting, or changing one letter
int main() {
    char word[16];
    int n = 0;
    int i, j, ret = 0;
    while(gets(word)) {
        int len = strlen(word);
        int mx = 0;
        string x = word;
        string y;
        map<string, int>::iterator it;
        for(i = 0; i <= len; i++) {//adding
            for(j = 'a'; j <= 'z'; j++) {
                y = x.substr(0, i) + (char)j + x.substr(i);
                it = R[y.length()].find(y);
                if(it != R[y.length()].end())
                    mx = max(mx, dp[it->second]);
                if(y.compare(x) > 0)
                    break;
                //cout << y << y.compare(x) << endl;
            }
        }
        for(i = 0; i < len; i++) {//deleting
            y = x.substr(0, i) + x.substr(i+1);
            it = R[y.length()].find(y);
            if(it != R[y.length()].end())
                mx = max(mx, dp[it->second]);
            //cout << y << endl;
        }
        y = x;
        for(i = 0; i < len; i++) {//changing
            for(j = 'a'; j <= 'z'; j++) {
                char o = y[i];
                y[i] = j;
                it = R[y.length()].find(y);
                if(it != R[y.length()].end())
                    mx = max(mx, dp[it->second]);
                //cout << y << endl;
                y[i] = o;
                if(y.compare(x) > 0)
                    break;
            }
        }
        dp[n] = mx+1;
        ret = max(ret, dp[n]);
        R[x.length()][x] = n;
        n++;
    }
    printf("%d\n", ret);
    return 0;
}

---

// 使用 hash function + map 速度更快
#include <stdio.h>
#include <string.h>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;

int dp[25005];
map<string, int> R[10007];
//adding, deleting, or changing one letter
unsigned int fnv_hash (const void* key, int len) {
    unsigned char* p = (unsigned char *)key;
    unsigned int h = 2166136261UL;
    int i;
    for (i = 0; i < len; i++)
        h = (h*16777619) ^ p[i];
    return h;
}
int main() {
    char word[16];
    int n = 0;
    int i, j, ret = 0;
    while(gets(word)) {
        int len = strlen(word);
        int mx = 0;
        string x = word;
        string y;
        map<string, int>::iterator it;
        unsigned int h;
        for(i = 0; i <= len; i++) {//adding
            for(j = 'a'; j <= 'z'; j++) {
                y = x.substr(0, i) + (char)j + x.substr(i);
                h = fnv_hash(y.c_str(), y.length())%10007;
                it = R[h].find(y);
                if(it != R[h].end())
                    mx = max(mx, dp[it->second]);
                if(y.compare(x) > 0)
                    break;
                //cout << y << y.compare(x) << endl;
            }
        }
        for(i = 0; i < len; i++) {//deleting
            y = x.substr(0, i) + x.substr(i+1);
            h = fnv_hash(y.c_str(), y.length())%10007;
            it = R[h].find(y);
            if(it != R[h].end())
                mx = max(mx, dp[it->second]);
            //cout << y << endl;
        }
        y = x;
        for(i = 0; i < len; i++) {//changing
            for(j = 'a'; j <= 'z'; j++) {
                char o = y[i];
                y[i] = j;
                h = fnv_hash(y.c_str(), y.length())%10007;
                it = R[h].find(y);
                if(it != R[h].end())
                    mx = max(mx, dp[it->second]);
                //cout << y << endl;
                y[i] = o;
                if(y.compare(x) > 0)
                    break;
            }
        }
        dp[n] = mx+1;
        ret = max(ret, dp[n]);
        h = fnv_hash(x.c_str(), x.length())%10007;
        R[h][x] = n;
        n++;
    }
    printf("%d\n", ret);
    return 0;
}

---

// 使用 Trie, 速度最快的一個
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
struct Node {
    Node *next[26];
    int label;
    Node() {
        label = -1;
        memset(next, 0, sizeof(next));
    }
};
void insertTrie(const char *str, Node *root, int label) {
    static Node *p;
    static int i, idx;
    p = root;
    for(i = 0; str[i]; i++) {
        idx = str[i]-'a';
        if(p->next[idx] == NULL)
            p->next[idx] = new Node();
        p = p->next[idx];
    }
    p->label = label;
}
int findTrie(const char *str, Node *root) {
    static Node *p;
    static int i, idx;
    p = root;
    for(i = 0; str[i]; i++) {
        idx = str[i]-'a';
        p = p->next[idx];
        if(p == NULL)   return -1;
    }
    return p->label;
}
int dp[25005];
//adding, deleting, or changing one letter
int main() {
    char word[16];
    int n = 0;
    Node *root = new Node();
    int i, j, ret = 0;
    while(gets(word)) {
        int len = strlen(word);
        int mx = 0;
        int findret = -1;
        string x = word;
        string y;
        for(i = 0; i <= len; i++) {//adding
            for(j = 'a'; j <= 'z'; j++) {
                y = x.substr(0, i) + (char)j + x.substr(i);
                findret = findTrie(y.c_str(), root);
                if(findret >= 0)
                    mx = max(mx, dp[findret]);
                if(y.compare(x) > 0)
                    break;
                //cout << y << y.compare(x) << endl;
            }
        }
        for(i = 0; i < len; i++) {//deleting
            y = x.substr(0, i) + x.substr(i+1);
                findret = findTrie(y.c_str(), root);
                if(findret >= 0)
                    mx = max(mx, dp[findret]);
            //cout << y << endl;
        }
        y = x;
        for(i = 0; i < len; i++) {//changing
            for(j = 'a'; j <= 'z'; j++) {
                char o = y[i];
                y[i] = j;
                findret = findTrie(y.c_str(), root);
                if(findret >= 0)
                    mx = max(mx, dp[findret]);
                //cout << y << endl;
                y[i] = o;
                if(y.compare(x) > 0)
                    break;
            }
        }
        dp[n] = mx+1;
        ret = max(ret, dp[n]);
        insertTrie(x.c_str(), root, n);
        n++;
    }
    printf("%d\n", ret);
    return 0;
}