[leetcode]Word Ladder - java 深度和广度遍历

这道题可以考虑两种方式解决

1. 深度优先遍历

2. 广度优先遍历

 

其中算法的效率取决于数组中单词的顺序，如果解决方案靠前，那么深度优先所用时间短；如果解在中间的位置，那么广度优先用时较短

 

深度优先采用回溯递归调用的方式

public int ladderLengthTraceback(String start, String end, Set<String> dict) {
        List<String> words = new ArrayList<String>();
        List<String> result = new ArrayList<String>();
        backtrack(start, end, dict, words, result);
        if(result.isEmpty()){
            return 0;
        }
        return result.size()+1;
    }

    private void backtrack(String start, String end, Set<String> dict, List<String> words, List<String> result){
        if(start.equals(end)){
            if(result.isEmpty() || words.size() < result.size()){
                result.clear();
                result.addAll(words);
            }
            return;
        }else if (!result.isEmpty() && words.size()>= result.size()){
            return;
        }
        List<String> cw = new ArrayList<String>();
        for(int i=0; i<start.length(); i++){
            char[] startCharArray = start.toCharArray();
            for(int j=0; j<26; j++){
                startCharArray[i] = (char)('a' +j);
                String word = new String(startCharArray);
                if((dict.contains(word) && !words.contains(word)) || word.equals(end)){
                    cw.add(word);
                }
            }
        }
        for(String word : cw){
            int size = words.size();
            words.add(word);
            backtrack(word, end, dict, words, result);
            words.remove(size);
        }
    }

 

广度优先采用队列循环的方式

public int ladderLength(String start, String end, Set<String> dict){
        if (start == null || end == null || start.equals(end)
                || start.length() != end.length())
            return 0;

        if (isOneWordDiff(start, end))
            return 2;

        Queue<String> queue=new LinkedList<String>();
        HashMap<String,Integer> dist=new HashMap<String,Integer>();

        queue.add(start);
        dist.put(start, 1);

        while(!queue.isEmpty())
        {
            String head=queue.poll();

            int headDist=dist.get(head);
            //从每一个位置开始替换成a~z
            for(int i=0;i<head.length();i++)
            {
                for(char j='a';j<'z';j++)
                {
                    if(head.charAt(i)==j) continue;
                    char[] s = head.toCharArray();
                    s[i]=j;
                    String sb = new String(s);
                    if(sb.toString().equals(end)) return headDist+1;

                    if(dict.contains(sb.toString())&&!dist.containsKey(sb.toString()))
                    {
                        queue.add(sb.toString());
                        dist.put(sb.toString(), headDist+1);
                    }
                }
            }
        }

        return 0;
    }

    private boolean isOneWordDiff(String a, String b) {
        int diff = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                diff++;
                if (diff >= 2)
                    return false;
            }
        }

        return diff == 1;
    }