資訊專欄INFORMATION COLUMN
摘要：題目鏈接圖用，和題類似。要找到所有字母的，之后用存下入度為的字母，然后輸出。要記錄下每個字母對應(yīng)的所有字母，防止重復(fù)。求的過程可以用，從所有單詞的開始，對不同的字母存入度，相同的去下一層。
Alien Dictionary
題目鏈接：https://leetcode.com/problems...
圖用topological sort，和course schedule題類似。
要找到所有字母的indegree，之后用q存下入度為0的字母，然后輸出。要記錄下每個字母對應(yīng)的所有parent字母，防止重復(fù)。求indegree的過程可以用dfs，從所有單詞的index = 0開始，對不同的字母存入度，相同的去下一層。
注意invalid的情況：有環(huán)，如果出現(xiàn)兩個單詞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保存出現(xiàn)過的字母了。
bfs的方法：待做。。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66550.html
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...
摘要：拓?fù)渑判驈?fù)雜度時間空間思路首先簡單介紹一下拓?fù)渑判?，這是一個能夠找出有向無環(huán)圖順序的一個方法假設(shè)我們有條邊，先將每個節(jié)點(diǎn)的計(jì)數(shù)器初始化為。最后，我們開始拓?fù)渑判?，從?jì)數(shù)器為的字母開始廣度優(yōu)先搜索。 Alien Dictionary There is a new alien language which uses the latin alphabet. However, the ord...
摘要：題目鏈接題目分析給定一個單詞數(shù)組和一個字符串，判斷給定的數(shù)組是否滿足給定字符串的順序。思路按給定字符串，替換成正常順序的單詞。再判斷之前和之后的數(shù)組是否相同。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D61 953. Verifying an Alien Dictionary 題目鏈接 953. Verifying an Alien Dictionary 題目分析 給定一個單詞...
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...
摘要：本章主要介紹字典的概念，基本操作以及一些進(jìn)階操作。使用字典在中，字典是一系列鍵值對。中用花括號來表示字典。代碼定義空字典的語法結(jié)果如果要修改字典中的值，只需通過鍵名訪問就行。 《Python編程：從入門到實(shí)踐》筆記。本章主要介紹字典的概念，基本操作以及一些進(jìn)階操作。 1. 使用字典（Dict） 在Python中，字典是一系列鍵值對。每個鍵都與一個值相關(guān)聯(lián)，用鍵來訪問值。Python中用...
閱讀 709·2021-09-30 09:47
閱讀 2900·2021-09-04 16:40
閱讀 886·2019-08-30 13:18
閱讀 3478·2019-08-29 16:22
閱讀 1587·2019-08-29 12:36
閱讀 638·2019-08-29 11:11
閱讀 1503·2019-08-26 13:47
閱讀 1156·2019-08-26 13:32
