I got TLE, but I do not know why(Java)


  • 0
    W

    Can anyone help me to check why this code is TLE? I ran this code on my own laptop with same data input, it returned right away. Many thanks!

    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
            Queue<String> que = new ArrayDeque<String>();
            que.add(beginWord);
            HashMap<String, Integer> distmap = new HashMap<String, Integer>();
            distmap.put(beginWord, 1);
            while (que.size() > 0) {
                String word = que.remove();
                int dist = distmap.get(word);
                for (int i = 0; i < word.length(); i++) {
                    for(char c = 'a'; c <= 'z'; c++) {
                        char[] carr = word.toCharArray();
                        carr[i] = c;
                        String tmp = new String(carr);
                        if (!wordList.contains(tmp)) continue;
                        if (distmap.containsKey(tmp)) continue;
                        que.add(tmp);
                        distmap.put(tmp, dist+1);
                        if (tmp.equals(endWord)) return dist+1;
                    }                
                }
            }
            return 0;
        }
    
    

  • 0
    K

    Hate to say the OJ is picky, but you have to do a tiny change to make it work.
    Don't use String, use StringBuilder !

     public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
            
            HashMap<String, Integer> map = new HashMap();
            Queue<String> queue = new LinkedList();
            
            map.put(beginWord,1);
            queue.offer(beginWord);
            
            while (!queue.isEmpty()) {
                String word = queue.poll();
                
                for (int i = 0; i < word.length(); i++) {
                    String temp = word;
                    for (char c = 'a'; c <='z'; c++) {
                        StringBuilder sb = new StringBuilder(word);
                        sb.setCharAt(i,c);
                        temp = sb.toString();
                        if (temp.equals(endWord)) {
                            return map.get(word)+1;
                        }
                        
                        if (wordList.contains(temp) && map.get(temp) == null) {
                            map.put(temp, map.get(word)+1);
                            queue.offer(temp);
                        }
                    }
                }
            }
            
            return 0;
        }
    

Log in to reply
 

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