Anyone can pass the test?


  • 0
    L

    Even I copy the highly rated Two-end BFS java method, it is told me that Time Limit Exceeded. What happened here?


  • 0
    L

    Attached is my code. Feel confused..

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if(!wordList.contains(endWord)) {
                return 0;
            }
            Set<String> beginSet = new HashSet<>();
            Set<String> endSet = new HashSet<>();
            Set<String> visited = new HashSet<>();
            int len = 1;
            int slen = beginWord.length();
            beginSet.add(beginWord);
            endSet.add(endWord);
            while(!beginSet.isEmpty() && !endSet.isEmpty()) {
                if(beginSet.size() > endSet.size()) {
                    Set<String> t = beginSet;
                    beginSet = endSet;
                    endSet = t;
                }
                Set<String> tmp = new HashSet<>();
                for(String s: beginSet) {
                    char[] sc = s.toCharArray();
                    for(int i = 0; i < slen; i++) {
                        char old = sc[i];
                        for(char c = 'a'; c <= 'z'; c++) {
                            sc[i] = c;
                            String sn = new String(sc);
                            if(endSet.contains(sn)) return len + 1;
                            if(wordList.contains(sn)) {
                                wordList.remove(sn);
                                tmp.add(sn);
                            }
                        }
                        sc[i] = old;
                    }
                }
                beginSet = tmp;
                len++;
            }
            return 0;
    }
    

  • 0
    L

    I see, I need to change the List wordList to HashSet to reduce the search time...


  • 0
    C

    @lakecarrot I have the same problem! Do you mean changing the type of the parameter? Is it allowed to modify function signature?


  • 1
    L

    @asgdsfsfmc What I mean is transferring the List<> to Set<> in your function.
    like
    Set<String> wordSet = new HashSet<>(wordList);


  • 0
    E

    I have the same problem, tried all the highly rated answers but everyone ends with a TLE...


  • 0
    C

    @Enkri_

    create a set 'dictionary' with all elements in the wordList, and do not add the endWord to dictionary, you will pass the test.

    The TLE, due to list.contains(o) is O(n), while set.contains(o) is O(1).


Log in to reply
 

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