can someone help me analyze why it is time limit exceeded?


  • 0
    J

    Hi,
    I got a solution based on DFS search, but unfortunately, time exceeded. but I cannot see why. I definitely avoided loop like hot->dog->hot......, and I used backtracking, but still.
    can someone help me please? many thanks.

    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            Set<String> wordSet = new HashSet<>(wordList);
            Set<String> v = new HashSet<>();
            v.add(beginWord);
            List<List<String>> res = new ArrayList<>();
            PriorityQueue<List<String>> q = new PriorityQueue<>(10, new Comparator<List<String>>(){
                public int compare(List<String> a, List<String> b){
                    return a.size()-b.size();
                }    
            });
            List<String> tmp = new ArrayList<String>();
            tmp.add(beginWord);
            dfsHelper(beginWord, endWord, wordSet, q, tmp, v);
            while(!q.isEmpty()){
                List<String> sub = q.poll();
                if(res.size()!=0&&sub.size()>res.get(res.size()-1).size()){
                    break;
                }else{
                    res.add(sub);
                }
            }
            return res;
        }
        
        public void dfsHelper(String root, String endWord, Set<String> wordSet, PriorityQueue<List<String>> res, List<String> tmp, Set<String> visit){
            if(root.equals(endWord)){
                List<String> sub = new ArrayList<>(tmp);
                res.offer(sub);
                return;
            }
            for(String s : childWords(root, wordSet)){
                if(visit.contains(s)) continue;
                tmp.add(s);
                visit.add(s);
                dfsHelper(s, endWord, wordSet, res, tmp, visit);
                visit.remove(s);
                tmp.remove(s);
            }
        }
        
        public List<String> childWords(String root, Set<String> wordSet){
            List<String> ret = new ArrayList<>();
            for(int i = 0; i<root.length(); i++){
                for(char c = 'a'; c<='z'; c++){
                    if(root.charAt(i) == c) continue;
                    String r = replaceOne(c, i, root);
                    if(wordSet.contains(r)) ret.add(r);
                }
            }
            return ret;
        }
        
        public String replaceOne(char c, int index, String root){
            char[] carr = root.toCharArray();
            carr[index] = c;
            return new String(carr);
        }
    }
    

Log in to reply
 

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