Word Ladder II

https://leetcode.com/problems/word-ladder-ii/

Given two words (startandend), and a dictionary, find all shortest transformation sequence(s) fromstarttoend, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

For example,

Given:
start="hit"
end="cog"
dict=["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

All words have the same length.
All words contain only lowercase alphabetic characters.

解题思路：

似乎上一题比较笨的方法，放在这里正合适，因为要返回所有可能的最小路径。但是一直出错，总结一下，犯了一个错误。

这里的visited不能用来直接判断。因为同一层，前面已经加进来的词，在后面也是可以加进来的。比如abc-adc-aec，abc-afc，这里后面还是可以加入aec的。所以在每层的判断，实际上用的是本层往前的set。所以，在遍历新层，就要把前面的set给存起来，用来判断。

思路就是，本层如果有和end差一个字符的了，就不再转换，将本层判断结束，把所有可能的解放入最后的解集中。遍历每层的时候，都看这个解集是不是非空，非空就直接返回。

可是，写出来后，一直TLE。

网友提示，替换string的某一个字符，因为没有直接的方法，我是用两个substring去做。其实应该，先转化为char[]，再去给char[i]赋值，再转化为string，这样会快不少。结果就ac了。

public class Solution {
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> result = new ArrayList<List<String>>();
        List<String> current = new ArrayList<String>();
        Set<String> visited = new HashSet<String>();
        visited.add(start);
        current.add(start);
        result.add(current);
        
        List<List<String>> returnResult = new ArrayList<List<String>>();

        for (int i = 0; i < dict.size(); i++) {
            List<List<String>> temp = new ArrayList<List<String>>();
            Set<String> visitedBeforeThisLevel = new HashSet<String>(visited);
            for (List<String> list : result) {
                String last = list.get(list.size() - 1);
                if(differsOnlyOne(last, end)) {
                    List<String> tempresult = new ArrayList<String>(list);
                    tempresult.add(end);
                    returnResult.add(tempresult);
                    continue;
                }
                if(returnResult.size() > 0) {
                    continue;
                }
                
                char[] charArray = last.toCharArray();
                for(int j = 0; j < last.length(); j++) {
                    char originalChar = charArray[j];
                    for(char k = 'a'; k <= 'z'; k++) {
                        charArray[j] = k;
                        String newString = new String(charArray);  
                        if(dict.contains(newString) && !visitedBeforeThisLevel.contains(newString)) {
                            List<String> temp1 = new ArrayList<String>(list);
                            temp1.add(newString);
                            visited.add(newString);
                            temp.add(temp1);
                        }
                    }
                    charArray[j] = originalChar;
                }
            }
            if(returnResult.size() > 0) {
                return returnResult;
            }
            result = temp;
        }
        return result;
    }
    
    public boolean differsOnlyOne(String str1, String str2) {
        int differNum = 0;
        for (int i = 0; i < str1.length(); i++) {
            if(str1.charAt(i) != str2.charAt(i)) {
                differNum++;
            }
        }
        if(differNum == 1) {
            return true;
        }else {
            return false;
        }
    }
}

也可以不用differsOnlyOne这个方法，直接判断是否为end。

public class Solution {
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> result = new ArrayList<List<String>>();
        List<String> current = new ArrayList<String>();
        Set<String> visited = new HashSet<String>();
        visited.add(start);
        current.add(start);
        result.add(current);
        
        List<List<String>> returnResult = new ArrayList<List<String>>();

        for (int i = 0; i < dict.size(); i++) {
            List<List<String>> temp = new ArrayList<List<String>>();
            Set<String> visitedBeforeThisLevel = new HashSet<String>(visited);
            for (List<String> list : result) {
                String last = list.get(list.size() - 1);
                char[] charArray = last.toCharArray();
                boolean flag = true;
                for(int j = 0; j < last.length() && flag; j++) {
                    char originalChar = charArray[j];
                    for(char k = 'a'; k <= 'z'; k++) {
                        charArray[j] = k;
                        String newString = new String(charArray);
                        if(newString.equals(end)) {
                            list.add(end);
                            returnResult.add(list);
                            flag = false;
                            break;
                        }
                        if(dict.contains(newString) && !visitedBeforeThisLevel.contains(newString)) {
                            List<String> temp1 = new ArrayList<String>(list);
                            temp1.add(newString);
                            visited.add(newString);
                            temp.add(temp1);
                        }
                    }
                    charArray[j] = originalChar;
                }
            }
            if(returnResult.size() > 0) {
                return returnResult;
            }
            result = temp;
        }
        return result;
    }
}

上面两种方法的时间基本在1500ms左右，应该说是刚刚过关，距离大部队还有点远，只能看看有没有其他解法。

http://www.cnblogs.com/yuzhangcmu/p/4119492.html

在上面的地址里看到用HashMap的解法，key是当前已经到的string，也就是最后一个string，value是到这个string的所有可能路径，也就是一个List<List<String>>的类型。

答题思路和上面我的解法还是一致的，只不过这里用了map，循环也改成了queue。比较关键的是，当且仅当queue里面没有出现过新构造的newString的时候，才将其放入queue，注释里也写了。否则就会出现很多重复的newString，这也是开始我一直改用这个方法，也一直TLE的原因。

这个方法的耗时一般只要900-1000ms，比我上面的方法少了一半时间。原因就是，这里的queue仅仅存不同的string。所以对其变换的时候，也是将不同的string存入queue。这样就不会出现对每个相同的string都要做一次变换，来看看它可能的拓展，和是不是已经到end了。

反观我上面的方法，是用一个List<List<String>>的类型存储当前所有可能的路径，然后对其进行遍历，取出最后一个string进行变换。这样，最后一个string很多都是重复的，变换也变换了很多重复的次数。

这其实也是这个解法用hashmap的精髓。虽然数据结构复杂了点，但是能有效的降低时间。

代码如下。

public class Solution {
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        Map<String, List<List<String>>> path = new HashMap<String, List<List<String>>>();
        Queue<String> queue = new LinkedList<String>();
        Set<String> visited = new HashSet<String>();
        visited.add(start);
        queue.offer(start);
        
        List<List<String>> startpath = new ArrayList<List<String>>();
        List<String> startList = new ArrayList<String>();
        startList.add(start);
        startpath.add(startList);
        path.put(start, startpath);
        
        int size = queue.size();
        while (queue.size() > 0) {
            size = queue.size();
            Set<String> visitedBeforeThisLevel = new HashSet<String>(visited);
            Map<String, List<List<String>>> pathBeforeThisLevel = new HashMap<String, List<List<String>>>(path);
            while(size > 0){
                String last = queue.poll();
                char[] charArray = last.toCharArray();
                boolean flag = true;
                for(int j = 0; j < last.length() && flag; j++) {
                    char originalChar = charArray[j];
                    for(char k = 'a'; k <= 'z'; k++) {
                        charArray[j] = k;
                        String newString = new String(charArray);
                        if((dict.contains(newString) || newString.equals(end)) && !visitedBeforeThisLevel.contains(newString)) {
                            List<List<String>> lastPath = path.get(last);
                            List<List<String>> extendedPath = new ArrayList<List<String>>();
                            // AC的关键，不能放在这里，应该放在下面。只有在newString不在queue里的时候才加入，否则会加入多个
                            // queue.offer(newString);
                            // visited.add(newString);
                            if(path.containsKey(newString)) {
                                extendedPath = path.get(newString);
                            } else {
                                queue.offer(newString);
                                visited.add(newString);
                                path.put(newString, extendedPath);
                            }
                            for(List<String> list : lastPath) {
                                List<String> newList = new ArrayList<String>(list);
                                newList.add(newString);
                                extendedPath.add(newList);
                            }
                            // 不用每次都put，因为extendedPath是引用，第一次put进去，以后直接改就可以
                            // path.put(newString, extendedPath);
                        }
                        if(newString.equals(end)) {
                            flag = false;
                            break;
                        }
                    }
                    charArray[j] = originalChar;
                }
                size--;
            }
            if(path.containsKey(end)) {
                return path.get(end);
            }
        }
        return new ArrayList<List<String>>();
    }
}

这里总结一下，本题克服TLE，最终AC的两点关键：

1. String替换某位的字符，不能用substring，要先转化为char[]。

实际上，先把string转化为StringBuffer sb，再sb.setCharAt(j, k);也是可以的，但还是比char[]要慢一点。

2. 用hashmap，能有效降低时间复杂度。

优质内容筛选与推荐>>
1、C语言I博客作业07
2、Bootstrap 表格
3、HTTP_REFERER
4、Regular进阶：跨组件通信
5、Oracle从入门到精通限定查询和排序查询的问题

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看