https://leetcode.com/problems/minimum-genetic-mutation/

// 这个方法特别好
// https://discuss.leetcode.com/topic/63959/c-two-end-bfs-solution-exactly-same-as-127-word-ladder
// 提到与 https://leetcode.com/problems/word-ladder/ 127. Word Ladder 题目其实是一模一样的
// 看了一下，的确是的

public class Solution {
    // 这个题目里面用到了两面BFS的方法,然后通过对字符串的替换,来降低优先级
    // 之前另一个题目 Word Ladder里面,用的是一端到另一端的
    // 现在这个更巧妙一些,因为从set里面找结果,比遍历set的内容要更高效一些
    public int minMutation(String start, String end, String[] bank) {
        Set<String> dict = new HashSet(Arrays.asList(bank));
        if (!dict.contains(end)) {
            return -1;
        }

        Set<String> lessSet = new HashSet();
        Set<String> moreSet = new HashSet();

        char[] chList = {‘A‘, ‘C‘, ‘G‘, ‘T‘};

        lessSet.add(start);
        moreSet.add(end);
        int step = 0;
        while (true) {

            // wrong: if dict is empty, no need to check more
            // right: check lessSet
            if (lessSet.isEmpty()) {
                return -1;
            }

            if (moreSet.size() < lessSet.size()) {
                Set<String> tmp = lessSet;
                lessSet = moreSet;
                moreSet = tmp;
            }
            //printSet(lessSet, moreSet, dict);

            step++;
            Iterator<String> iter = lessSet.iterator();
            Set<String> newSet = new HashSet();
            while(iter.hasNext()) {
                String str = iter.next();
                for (int i=0; i<str.length(); i++) {
                    StringBuilder sb =new StringBuilder(str);
                    for (int j=0; j<4; j++) {
                        if (str.charAt(i) == chList[j]) {
                            continue;
                        }

                        sb.setCharAt(i, chList[j]);
                        if (moreSet.contains(sb.toString())) {
                            return step;
                        }

                        if (dict.contains(sb.toString())) {
                            dict.remove(sb.toString());
                            newSet.add(sb.toString());

                        }

                    }
                }
            }
            lessSet = newSet;
        }
    }

    private void printSet(Set<String> lessSet, Set<String> moreSet, Set<String>dict) {
        System.out.printf("Here is lessSet:");
        Iterator<String> iter = lessSet.iterator();
        while (iter.hasNext()) {
            System.out.printf("%s,", iter.next());
        }
        System.out.println();
        System.out.printf("Here is moreSet:");
        iter = moreSet.iterator();
        while (iter.hasNext()) {
            System.out.printf("%s,", iter.next());
        }
        System.out.println();
        System.out.printf("Here is dict:");
        iter = dict.iterator();
        while (iter.hasNext()) {
            System.out.printf("%s,", iter.next());
        }
        System.out.println();
        System.out.println("################");

    }
}