My solution using BFS get TLE,could anyone help me fix it?


  • 0
    V
    public class Solution {
        public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
            return search(beginWord,endWord,wordDict);
        }
        private int search(String beginWord, String endWord, Set<String> wordDict){
            Queue<String> q = new ArrayDeque<String>();
            int depth = 0;
            int width = 0;
            String cur = null;
            q.offer(beginWord);
            while(!q.isEmpty()){
                depth++;
                width = q.size();
                while(width-->0){
                    cur = q.poll();
                    if(can(cur,endWord)){
                        return depth+1;
                    }
                    Iterator<String> it = wordDict.iterator();  
                    while(it.hasNext()){  
                        String s = it.next();  
                        if(can(cur,s)){
                        	q.offer(s);
                            it.remove();  
                        }  
                    }
                }
            }
            return 0;
        }
        private boolean can(String s,String t){
            int n = s.length();
            int count = 0;
            for(int i = 0;i<n;i++){
                if(s.charAt(i)!=t.charAt(i)){
                    count++;
                }
                if(count>1){
                    break;
                }
            }
            return count==1;
        }
    }

  • 0
    D
    Iterator<String> it = wordDict.iterator();  
    while(it.hasNext()){  
        String s = it.next();  
        if(can(cur,s)){
            q.offer(s);
            it.remove();  
        }  
    }
    

    For this part, if too many words in wordDict, it will be TLE. So for the String 'cur', you can change each character of 'cur',replaced from 'a' to 'z',then check the new 'cur' is in wordDict or not, if so, add it to the queue 'q', time complexity is reduced.

    And for this problem,it's like searching the path in a graph by using BFS,so make sure the same word could be added to queue only once,and the first path you found is the shortest one.


Log in to reply
 

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