UVa_10029_Edit_Step_Ladders.java

Problem Links:

uva10029, poj2564, zoj1876(not passed),

Problem:

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

Sample Input

cat
dig
dog
fig
fin
fine
fog
log
wine

Sample Output

5

---

Source Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        list = new ArrayList<String>();
        String strLine = null;
        while ((strLine = br.readLine()) != null && strLine.length() > 0) {
            list.add(strLine);
        }
        // System.out.println("Input read done");
        N = list.size();
        cost = new int[N + 1];
        cost[0] = 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;
    }
}