一亩三分地论坛

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

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

[Leetcode] 请问Word Ladder 1 和 2的时间空间复杂度分别是多少?

[复制链接] |试试Instant~ |关注本帖
oio14644 发表于 2016-12-1 02:20:17 | 显示全部楼层 |阅读模式

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

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

x

Word Ladder
public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        wordList.remove(beginWord);
        int level = 1;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                String s = q.remove();
                for(int j = 0; j < s.length(); j++){
                    for(char c = 'a'; c <= 'z'; c++){
                        char[] cc = s.toCharArray();//start from the original string
                        cc[j] = c;
                        String next = new String(cc);
                        if(next.equals(endWord)){
                            return level + 1;
                        }else if(wordList.contains(next)){
                            q.add(next);
                            wordList.remove(next);
                        }
                    }
                }
            }
            level++;
        }
        return 0;
    }
}

Word Ladder 2

public class Solution {
    HashMap<String, Integer> map = new HashMap<>();
    List<List<String>> res = new ArrayList<>();
    List<String> list = new ArrayList<>();
    public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
        getDistanceFromBegin(beginWord, endWord, wordList);
        helper(beginWord, endWord);
        return res;
    }
    public void helper(String beginWord, String endWord){
        if(endWord.equals(beginWord)){
            List<String> cur = new ArrayList<>(list);
            cur.add(beginWord);
            Collections.reverse(cur);
            res.add(cur);
            return;
        }
        list.add(endWord);
        for(int i = 0; i < endWord.length(); i++){
            for(char c = 'a'; c <= 'z'; c++){
                char[] cc = endWord.toCharArray();
                cc = c;
                String pre = new String(cc);
                if(map.containsKey(pre) && map.get(pre) + 1 == map.get(endWord)){
                    helper(beginWord, pre);
                }
            }
        }
        list.remove(list.size() - 1);
    }
    public void getDistanceFromBegin(String beginWord, String endWord, Set<String> wordList){
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        wordList.remove(beginWord);
        int level = 1;
        map.put(beginWord, level);
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                String s = q.remove();
                for(int j = 0; j < s.length(); j++){
                    for(char c = 'a'; c <= 'z'; c++){
                        char[] cc = s.toCharArray();//start from the original string
                        cc[j] = c;
                        String next = new String(cc);
                        if(next.equals(endWord)){
                            map.put(next, level + 1);
                            return;
                        }else if(wordList.contains(next)){
                            q.add(next);
                            wordList.remove(next);
                            map.put(next, level + 1);
                        }
                    }
                }
            }
            level++;
        }
    }
}

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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