Only Use BFS level-order traversal Java Solution


  • 0
    S

    In order to pass this case:

    start = 'red'

    end = 'tax'

    dict = ['ted', rad', 'tad']

    since we cannot use a node twice, whether BFS or DFS will give us

    either red->ted->tad->tax

    or red->rad->tad->tax

    because 'tad' is a common word in two paths.

    I use a set to collect all the words appear at current level, and then delete them from dict after I go over each word in current level. And also use a deque to store the paths on the fly.This code cost 1000ms.

    public class Solution {
        public List<List<String>> findLadders(String start, String end, Set<String> dict) {
            List<List<String>> rslt = new ArrayList<List<String>>();
            Deque<List<String>> paths = new LinkedList<List<String>>();
            boolean found = false;
            
            // initialize path
            List<String> path = new ArrayList<String>();
            path.add(start);
            paths.offerLast(path);
            
            // add end to dictionary, remove start from dict
            dict.add(end);
            if(dict.contains(start)) dict.remove(start);
            
            // BFS
            while(!found && !paths.isEmpty()){
                Set<String> set = new HashSet<String>();
                int k = paths.size();
                for(int i = 0;i < k;i++){
                    List<String> list = paths.pollFirst();
                    String s = list.get(list.size()-1);
                    for(String t : neighbors(s, dict)){
                        set.add(t);
                        List<String> newList = new ArrayList<String>(list);
                        newList.add(t);
                        paths.offerLast(newList);
                        if(t.equals(end)){
                            found = true;
                            rslt.add(newList);
                        }
                    }
                }
                dict.removeAll(set);
            }
            return rslt;
        }
        
        private List<String> neighbors(String s, Set<String> dict){
            List<String> list = new ArrayList<String>();
            char[] chars = s.toCharArray();
            for(int j = 0;j < s.length();j++){
                char original = chars[j];
                for(char c = 'a';c <= 'z';c++){
                    chars[j] = c;
                    String t = new String(chars);
                    if(dict.contains(t)) list.add(t);
                }
                chars[j] = original;
            }
            return list;
        }
    }
    

    A little trick here is to use char[] array to carry the String first, replacing char on char array save a lot time regarding using String.substring()


  • 0
    W

    translate your code into c++ then TLE happens...
    i use vector to replace list here, i don't know what's wrong...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.