2013-05-04 14:24:43Morris
[UVA][dp] 10029 - Edit Step Ladders
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
雖然這題是要求挑一個最長字典順序，而相鄰兩個單字可以藉由增加，刪除，修改達到。
不可能一個一個去比較，因此要窮舉可以修改成什麼，然後去做查找。
// 使用 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;
}