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("################");

    }

}