## Monday, March 12, 2012

uva10029, poj2564, zoj1876(not passed),

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

```cat
dig
dog
fig
fin
fine
fog
log
wine
```

`5`

## Source Code:

import java.util.ArrayList;
import java.util.List;

/**
* Problem 10029, Edit Step Ladders
* Solution: The main idea is using DP to calculate the longest step distance by
* the ith word. It's necessary to try all the possible operation, which
* includes change, add, and delete. Each operation is one step distance. Then,
* the best part is using binary search to check the updated word with one step
* distance based on the current word in the dictionary(list).
*/

/**
* @author antonio081014
* @since Mar 10, 2012, 4:19:33 PM
*/
class Main {

private List<String> list;
private int          N;
private int[]        cost;

public static void main(String[] args) throws Exception {
Main main = new Main();
main.run();
System.exit(0);
}

public void run() throws Exception {
list = new ArrayList<String>();
String strLine = null;
while ((strLine = br.readLine()) != null && strLine.length() > 0) {
}
// System.out.println("Input read done");
N = list.size();
cost = new int[N + 1];
cost = 1;
String a;
int max = 0;
for (int i = 1; i < N; i++) {
cost[i] = 1;
strLine = list.get(i);
int len = strLine.length();
for (int flag = 0; flag < 3; flag++) {
for (int j = 0; j < len; j++) {
for (int k = 0; k < 26; k++) {
a = trans(strLine, (char) ('a' + k), j, flag);
if (strLine.compareTo(a) < 0) {
break;
}
int mid = binarySearch(a, i);
if (mid >= 0 && cost[i] < cost[mid] + 1)
cost[i] = cost[mid] + 1;
}
}
}
for (int k = 0; k < 26; k++) {
a = trans(strLine, (char) ('a' + k), len, 0);
if (strLine.compareTo(a) < 0) {
break;
}
int mid = binarySearch(a, i);
if (mid >= 0 && cost[i] < cost[mid] + 1)
cost[i] = cost[mid] + 1;
}
if (cost[i] > max)
max = cost[i];
}
System.out.println(max);
}

public String add(String a, char c, int idx) {
return a.substring(0, idx) + c + a.substring(idx);
}

public String del(String a, int idx) {
return a.substring(0, idx) + a.substring(idx + 1);
}

public String chg(String a, char c, int idx) {
return a.substring(0, idx) + c + a.substring(idx + 1);
}

public String trans(String a, char c, int idx, int flag) {
switch (flag) {
case 0:
return add(a, c, idx);
case 1:
return del(a, idx);
default:
return chg(a, c, idx);
}
}

// The boundary is different.
public int binarySearch(String s, int end) {
int left = 0;
int right = end - 1;
while (left <= right) {
int mid = ((left + right) / 2);
int tmp = s.compareTo(list.get(mid));
if (tmp == 0)
return mid;
else if (tmp < 0)
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
}