word ladder 1.5 如果被challenge用26个char iteration太慢的话，大家怎么optimize？

同关注+1

ausgoo 发表于 2016-12-10 02:29
回答twoEnd BFS? 在leetcode discuss上有详解。 我自己试了下，快很多。谢谢。

two way bfs 不知道面试官给不给用 a-z 的enumeration...

RE .... 感觉这个非常值得讨论, 同关注!! +1

solarsys 发表于 2016-11-29 03:23
trieNode 接hashmap  hashmap 的value 继续是trieNode 这样每次获取只有O1

这也不是O（1）吧， worst case还是每次都是O（26）？

可以预处理得到一个graph，每个单词是一个graph node，(V1, V2) is in Edges iff diff(V1, V2) == 1

最近都没上自己的账号 不过仔细想了想好像hashmap的方法好像是自己误入歧途了。。大家请无视我的误导

贴个我自己polish过的版本，
   while 处理queue时不用再遍历size.
                //int len = queue.size();
                //for (int i = 0; i < len; i++) {

Map<String, Set<String>> oneCharDiffWords = new HashMap<>();
        Map<String, String> ancestorMap = new HashMap<>();         
        public List<String> ladderLength(String start, String end, List<String> words) {
            List<String> list = new ArrayList<>(words);
            if (start.equals(end))
                return null;
            list.add(start);
            list.add(end);
            for (String S : list) {
                 Set<String> set = new HashSet<>();
                 for (String T : list)
                     if (!S.equals(T) && isOneCharDiff(S, T))
                         set.add(T);
               
                 oneCharDiffWords.put(S, set);
            }
            Queue<String> queue = new LinkedList<>();
            Set<String> seen = new HashSet<>();
            queue.offer(start);
            seen.add(start);
            while (!queue.isEmpty()) {
                //int len = queue.size();
                //for (int i = 0; i < len; i++) {
                    String cur = queue.poll();
                    Set<String> oneCharDiffWordsSet = oneCharDiffWords.get(cur);
                    for (String str : oneCharDiffWordsSet) {
                        if (seen.add(str)){
                                ancestorMap.put(str, cur);
                            queue.offer(str);
                        }
                        if (str.equals(end)) return CreatePathFromAncestorMap(str);
                    }
                //}
            }
            return new ArrayList<String>();
        }

        private List<String> CreatePathFromAncestorMap(String end){
            List<String> res = new ArrayList<>();
            String ancestor=end;
            while(ancestor!=null){
                res.add(0, ancestor);
                ancestor=ancestorMap.get(ancestor);
            }
            return res;
        }

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

        public static void main(String[] args) {
                WordLadder1Dot5Way sol = new WordLadder1Dot5Way();
            List<String> res= sol.ladderLength("hit", "lib", new ArrayList<String>(Arrays.asList("cit", "cib", "lib", "hib")));
            for(String s: res) System.out.print(" "+ s);
        }

关注一下

春山寒 发表于 2016-11-28 11:32
是不是可以用trie来做 在每个position 只变化相同level trie里面有的字母

应该是用这个方法，但是感觉速度也不会提高很多