<
查看: 805|回复: 4
收起左侧

[Leetcode] word ladder总过不了一个test case

|只看干货
小水 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (70)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
code如下,其他case都能通过,不明白为什么对于beginword:"lost", endword:"cost",["most","fist","lost","cost","fish"],到最后不执行res++;
[Java] 纯文本查看 复制代码
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<String>(wordList);
        if(dict == null) return 0;
        Queue<String> q = new LinkedList<String>();
        q.offer(beginWord);
        int res = 1;
        while(!q.isEmpty()){
            int size = q.size();
            for(int n = 0; n < size; n++){
            String temp = q.poll();
            if (temp.equals(endWord)) return res;
            
            for(int i = 0; i < temp.length(); i++){
                for(char c = 'a'; c <= 'z'; c++){
                    String newWord = temp.substring(0, i) + c + temp.substring(i + 1);
                    if(dict.contains(newWord) && !newWord.equals(temp)){
                        dict.remove(newWord);
                        q.offer(newWord);
                    }
                }
            }
                
          }
            res++;
        }
        return 0;
    }




补充内容 (2020-3-17 00:40):
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int[] res = new int[1];
        Set<String> dict = new HashSet<String>(wordList);
        Set<String> begi...

补充内容 (2020-3-17 00:46):
我贴错code了,有问题的code在三楼……

上一篇:最近是变简单了吗 WEEKLY CONTEST
下一篇:有必要学functional programming language吗?
sanchaji 2020-3-17 02:06:22 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
第8行: i < queue.size()
Java中不能这样写, queue的size是动态的, 你要for循环同一层的单词必须先把size单拿出来: int size = queue.size()
我试过, 改了可以通过
回复

使用道具 举报

sanchaji 2020-3-16 23:45:34 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
我拿你的code跑这个test case过了, 在leetcode上也能AC, 为啥你说过不了

评分

参与人数 1大米 +1 收起 理由
小水 + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

 楼主| 小水 2020-3-17 00:41:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (70)
 
 
0% (0)    👎
本帖最后由 小水 于 2020-3-17 00:45 编辑
sanchaji 发表于 2020-3-16 23:45
我拿你的code跑这个test case过了, 在leetcode上也能AC, 为啥你说过不了

我贴错code了,这个是那份跑不过
[Java] 纯文本查看 复制代码
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        Set<String> dict = new HashSet<String>(wordList);
        LinkedList<String> queue = new LinkedList<String>();
        queue.add(beginWord);
        int res = 1;
        while(!queue.isEmpty()){
            for (int i = 0; i < queue.size(); i++){
                String word = queue.pop();
                if (word.equals(endWord)) return res;
                char[] chars = word.toCharArray();
                for (int j = 0; j < chars.length; j++){
                    char old = chars[j];
                    for (char c = 'a'; c <= 'z'; c++){
                        chars[j] = c;
                        String newWord = new String(chars);
                        if (dict.contains(newWord) && !newWord.equals(word)){
                            queue.add(newWord);
                            dict.remove(newWord);
                        }
                    }
                    chars[j] = old;
                }
            }
            res++;
        }
        return 0;
    }


回复

使用道具 举报

 楼主| 小水 2020-3-18 13:37:30 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (70)
 
 
0% (0)    👎
找到原因了,快把我改(chun)哭了TT,是因为我一开始没有存下来queue的长度值,queue的长度是动态变化的
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

>
快速回复 返回顶部 返回列表