一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 345|回复: 3
收起左侧

[算法题] 求教leetcode word ladder中的时间复杂度问题

[复制链接] |试试Instant~ |关注本帖
snl 发表于 2016-10-10 06:23:13 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
leetcode的word ladder这道题:https://leetcode.com/problems/word-ladder/
九章给的解法是:
http://www.jiuzhang.com/solutions/word-ladder/
其中判断wordList中有哪些与word相邻的String时,是将word的每一个字符都从a到z变换一遍再看wordList里有没有符合的
我觉得这种方法的算法复杂度是
word.length() * 26 * wordList.size()
(我假设set.contains()的复杂度是O(n))

我想的方法是,将word与wordList当中的String逐一比较是否相邻
所以复杂度是
word.size() * wordList.size()

但是九章的算法过了所有的测试点,我的出现了time limit exceeded

是我哪里想错了呢


九章的代码:
private String replace(String s, int index, char c) {        char[] chars = s.toCharArray();        chars[index = c;        return new String(chars);    }        // get connections with given word.    // for example, given word = 'hot', dict = {'hot', 'hit', 'hog'}    // it will return ['hit', 'hog']    private ArrayList<String> getNextWords(String word, Set<String> dict) {        ArrayList<String> nextWords = new ArrayList<String>();        for (char c = 'a'; c <= 'z'; c++) {            for (int i = 0; i < word.length(); i++) {                if (c == word.charAt(i)) {                    continue;                }                String nextWord = replace(word, i, c);                if (dict.contains(nextWord)) {                    nextWords.add(nextWord);                }            }        }        return nextWords;    }
我的代码:private List<String> neighbors(String x, Set<String> s){        Iterator<String> iter = s.iterator();        List<String> result = new ArrayList<String>();                while(iter.hasNext()){            String tmp = iter.next();            if(ifN(x, tmp)){                result.add(tmp);            }        }        return result;    }    private boolean ifN(String a, String b){        int l = a.length();        int count = 0;        for(int i = 0; i < l; i++){            if(a.charAt(i) != b.charAt(i)){                count++;            }            if(count > 1){                return false;            }        }        return true;    }
 楼主| snl 发表于 2016-10-10 06:24:40 | 显示全部楼层
九章的代码
  1. private String replace(String s, int index, char c) {
  2.         char[] chars = s.toCharArray();
  3.         chars[index] = c;
  4.         return new String(chars);
  5.     }
  6.    
  7.     // get connections with given word.
  8.     // for example, given word = 'hot', dict = {'hot', 'hit', 'hog'}
  9.     // it will return ['hit', 'hog']
  10.     private ArrayList<String> getNextWords(String word, Set<String> dict) {
  11.         ArrayList<String> nextWords = new ArrayList<String>();
  12.         for (char c = 'a'; c <= 'z'; c++) {
  13.             for (int i = 0; i < word.length(); i++) {
  14.                 if (c == word.charAt(i)) {
  15.                     continue;
  16.                 }
  17.                 String nextWord = replace(word, i, c);
  18.                 if (dict.contains(nextWord)) {
  19.                     nextWords.add(nextWord);
  20.                 }
  21.             }
  22.         }
  23.         return nextWords;
  24.     }
复制代码

我的代码
  1. private List<String> neighbors(String x, Set<String> s){
  2.         Iterator<String> iter = s.iterator();
  3.         List<String> result = new ArrayList<String>();
  4.         
  5.         while(iter.hasNext()){
  6.             String tmp = iter.next();
  7.             if(ifN(x, tmp)){
  8.                 result.add(tmp);
  9.             }
  10.         }
  11.         return result;
  12.     }
  13.     private boolean ifN(String a, String b){
  14.         int l = a.length();
  15.         int count = 0;
  16.         for(int i = 0; i < l; i++){
  17.             if(a.charAt(i) != b.charAt(i)){
  18.                 count++;
  19.             }
  20.             if(count > 1){
  21.                 return false;
  22.             }
  23.         }
  24.         return true;
  25.     }
复制代码
回复 支持 反对

使用道具 举报

stellari 发表于 2016-10-10 17:38:02 | 显示全部楼层
首先, 令L为单词长度, N为单词数目, 那么Set.contain()的平均复杂度一般是O(L). 所以, jiuzhang的算法的复杂度是26 * O(L) * O(L) = O(26L^2). 而你的算法则是O(LN). 至于哪种算法更优, 要看dict的L和N哪个更大. 实际的字典一般都满足N >> L, 所以jiuzhang的算法执行效果会更好.

回复 支持 反对

使用道具 举报

小乙 发表于 2016-10-11 09:06:53 | 显示全部楼层
从hash table里面寻找的时间复杂度是O(1)。 九章的时间复杂度是O(word.length() * 26 * 1) = O(word.length()), 常数可以省略的。
你的做法的时间复杂度是O(word.length() * wordList.size()) = O(word.length() * n)
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 10:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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