Alien Dictionary

gaomysion 發布于2019-08-14 17:18 / 1916人閱讀

摘要：題目鏈接圖用，和題類似。要找到所有字母的，之后用存下入度為的字母，然后輸出。要記錄下每個字母對應的所有字母，防止重復。求的過程可以用，從所有單詞的開始，對不同的字母存入度，相同的去下一層。

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的方法：待做。。

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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