Can someone tell me what the problem of my solution


  • 0
    K

    I use a two dimension array to store the ladder of every two word(include beginWord and endWord),in which 1 means can reach 0 means cannot .Then scan the array by bfs and maintain a visit array.But it will TLE when the case is
    "qa"
    "sq"
    ["si","go","se","cm","so","ph","mt","db","mb","sb","kr","ln","tm","le","av","sm","ar","ci","ca","br","ti","ba","to","ra","fa","yo","ow","sn","ya","cr","po","fe","ho","ma","re","or","rn","au","ur","rh","sr","tc","lt","lo","as","fr","nb","yb","if","pb","ge","th","pm","rb","sh","co","ga","li","ha","hz","no","bi","di","hi","qa","pi","os","uh","wm","an","me","mo","na","la","st","er","sc","ne","mn","mi","am","ex","pt","io","be","fm","ta","tb","ni","mr","pa","he","lr","sq","ye"]

    I don't why?? can some body tell me the reason?

    public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            wordList.remove(beginWord);
            wordList.remove(endWord);
            
            int len = wordList.size()+2;
            
            int[][] bp = new int[len][len];
            String[] wordArray = new String[len];
            wordArray[0] = beginWord;
            wordArray[len-1] = endWord;
            // convert to array
            int n = 1;
            for(String s : wordList)
            	wordArray[n++] = s;
            
            for(int i = 0;i < len-1;i++){
                for(int j = i+1;j < len;j++){
                    bp[i][j] = bp[j][i] = ladder(wordArray[i], wordArray[j]);
                }
            }
            
            List<List<String>> res = new ArrayList<List<String>>();
            
            bfs(bp, wordArray, new HashSet<Integer>(), res, new ArrayList<String>(), 0);
            
            return res;
        }
        
        public void bfs(int[][] bp, String[] list, HashSet<Integer> vist, List<List<String>> res, List<String> temp, int i){
            
            HashSet<Integer> vist2 = new HashSet<Integer>(vist);
            vist2.add(i);
            
            List<String> temp2 = new ArrayList<>(temp);
            temp2.add(list[i]);
            
        	if (i == list.length-1) {
                // get the shortest path:not good method though
                if (res.size() == 0){
                    res.add(temp2);
                } else {
                    if (res.get(0).size() > temp2.size()){
                        res.clear();
                        res.add(temp2);
                    } else if(res.get(0).size() == temp2.size()){
                        res.add(temp2);
                    }
                }
                return;
            }
            
            for(int j = 0; j < list.length;j++){
                if (!vist2.contains(j) && bp[i][j] == 1){
                    bfs(bp, list, vist2, res, temp2, j);
                }
            }
            
        }
        
        public int ladder(String s1, String s2){
            int l = 0;
            for(int i = 0;i < s1.length();i++){
                if (s1.charAt(i) != s2.charAt(i)) {
                    if (l == 0)l++;
                    else return 0;
                }
            }
            
            return l;
        }
    

Log in to reply
 

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