Alien Dictionary

gaomysion 发布于2019-08-14 17:18 / 1915人阅读

摘要：题目链接图用，和题类似。要找到所有字母的，之后用存下入度为的字母，然后输出。要记录下每个字母对应的所有字母，防止重复。求的过程可以用，从所有单词的开始，对不同的字母存入度，相同的去下一层。

Alien Dictionary

题目链接：https://leetcode.com/problems...

图用topological sort，和course schedule题类似。
要找到所有字母的indegree，之后用q存下入度为0的字母，然后输出。要记录下每个字母对应的所有parent字母，防止重复。求indegree的过程可以用dfs，从所有单词的index = 0开始，对不同的字母存入度，相同的去下一层。

注意invalid的情况：有环，如果出现两个单词start相同，那么长度短的在前：["ab", "abc"]

public class Solution {
    public String alienOrder(String[] words) {
        init(words);
        getGraph(list, 0);
        if(!valid) return "";
        
        // find the character with indegree = 0
        Queue q = new LinkedList();
        for(int i = 0; i < indegree.length; i++) {
            if(indegree[i] == 0 && set.contains(i)) {
                q.offer((char) (i + "a"));
            }
        }
        
        String result = "";
        while(!q.isEmpty()) {
            char c = q.poll();
            result += c;
            // if indegree -> 0, add to the q
            for(Character child : parents.get(c - "a")) {
                if(--indegree[child - "a"] == 0) {
                    q.offer(child);
                }
            }
        }
        
        return result;
    }
    
    int[] indegree;
    List> parents;
    // record the appearred characters
    Set set = new HashSet();
    List list;
    boolean valid = true;
    
    private void init(String[] words) {
        indegree = new int[26];
        parents = new ArrayList();
        for(int i = 0; i < 26; i++) parents.add(new HashSet());
        
        list = new ArrayList();
        for(String word : words) {
            list.add(word);
            for(int i = 0; i < word.length(); i++) set.add(word.charAt(i) - "a");
        }
    }
    
    private void getGraph(List list, int level) {
        // base case
        if(list.size() == 0) return;
        
        for(int i = 0; i < list.size(); i++) {
            if(level >= list.get(i).length()) {
                continue;
            }
            char c = list.get(i).charAt(level);
            // record the string with the same character at current level
            List same = new ArrayList();
            same.add(list.get(i));
            for(int j = i+1; j < list.size(); j++) {
                String cur = list.get(j);
                if(cur.length() <= level) {
                    // same start, different len, [abc, ab] is invalid
                    valid = false;
                    continue;
                }
                // character in the same level has order
                else if(cur.charAt(level) != c) {
                    if(parents.get(c-"a").add(cur.charAt(level))) {
                        indegree[cur.charAt(level) - "a"]++;
                        if(parents.get(cur.charAt(level)-"a").contains(c)) valid = false;
                    }
                }
                else same.add(cur);
            }
            if(same.size() > 1) getGraph(same, level + 1);
        }
    }
}

indegree用hashmap更好，这样就不用多带带的再用个set保存出现过的字母了。
bfs的方法：待做。。

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66550.html

[LeetCode] 953. Verifying an Alien Dictionary

Problem In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters. Given a seque...

ghnor 2019-08-16 13:57 评论0 收藏0
[Leetcode] Alien Dictionary 外文字典

摘要：拓扑排序复杂度时间空间思路首先简单介绍一下拓扑排序，这是一个能够找出有向无环图顺序的一个方法假设我们有条边，先将每个节点的计数器初始化为。最后，我们开始拓扑排序，从计数器为的字母开始广度优先搜索。 Alien Dictionary There is a new alien language which uses the latin alphabet. However, the ord...

pkhope 2019-08-14 12:38 评论0 收藏0
Leetcode PHP题解--D61 953. Verifying an Alien Dictio

摘要：题目链接题目分析给定一个单词数组和一个字符串，判断给定的数组是否满足给定字符串的顺序。思路按给定字符串，替换成正常顺序的单词。再判断之前和之后的数组是否相同。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D61 953. Verifying an Alien Dictionary 题目链接 953. Verifying an Alien Dictionary 题目分析给定一个单词...

sshe 2019-07-01 12:46 评论0 收藏0
【LC总结】图、拓扑排序 (Course Schedule I, II/Alien Dictiona

Course Schedule Problem There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, whi...

gaara 2019-08-14 15:54 评论0 收藏0
Python学习之路5-字典

摘要：本章主要介绍字典的概念，基本操作以及一些进阶操作。使用字典在中，字典是一系列键值对。中用花括号来表示字典。代码定义空字典的语法结果如果要修改字典中的值，只需通过键名访问就行。《Python编程：从入门到实践》笔记。本章主要介绍字典的概念，基本操作以及一些进阶操作。 1. 使用字典（Dict）在Python中，字典是一系列键值对。每个键都与一个值相关联，用键来访问值。Python中用...

NicolasHe 2019-07-30 16:41 评论0 收藏0