資訊專欄INFORMATION COLUMN
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 sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.
Example 1:
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As "h" comes before "l" in this language, then the sequence is sorted.
Example 2:
Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As "d" comes after "l" in this language, then words[0] > words[1], hence the sequence is unsorted.
Example 3:
Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because "l" > "?", where "?" is defined as the blank character which is less than any other character (More info).
Note:
1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
All characters in words[i] and order are english lowercase letters.
class Solution {
public boolean isAlienSorted(String[] words, String order) {
int[] dict = new int[26];
for (int i = 0; i < order.length(); i++) {
int index = order.charAt(i)-"a";
if (dict[index] != 0) return false;
dict[index] = i;
}
for (int i = 0; i < words.length-1; i++) {
for (int j = i+1; j < words.length; j++) {
int len = Math.min(words[i].length(), words[j].length());
int index = 0;
while (index < len) {
char ci = words[i].charAt(index);
char cj = words[j].charAt(index);
if (ci == cj) {
index++;
if (index == len && index < words[i].length()) return false;
} else {
if (dict[ci-"a"] > dict[cj-"a"]) return false;
break;
}
}
}
}
return true;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72628.html
摘要：題目鏈接題目分析給定一個單詞數(shù)組和一個字符串，判斷給定的數(shù)組是否滿足給定字符串的順序。思路按給定字符串，替換成正常順序的單詞。再判斷之前和之后的數(shù)組是否相同。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D61 953. Verifying an Alien Dictionary 題目鏈接 953. Verifying an Alien Dictionary 題目分析 給定一個單詞...
摘要：拓撲排序復雜度時間空間思路首先簡單介紹一下拓撲排序，這是一個能夠找出有向無環(huán)圖順序的一個方法假設(shè)我們有條邊，先將每個節(jié)點的計數(shù)器初始化為。最后，我們開始拓撲排序，從計數(shù)器為的字母開始廣度優(yōu)先搜索。 Alien Dictionary There is a new alien language which uses the latin alphabet. However, the ord...
摘要：題目鏈接圖用，和題類似。要找到所有字母的，之后用存下入度為的字母，然后輸出。要記錄下每個字母對應(yīng)的所有字母，防止重復。求的過程可以用，從所有單詞的開始，對不同的字母存入度，相同的去下一層。 Alien Dictionary 題目鏈接：https://leetcode.com/problems... 圖用topological sort，和course schedule題類似。要找到所有...
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...
Problem Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one po...
閱讀 1473·2023-04-25 16:31
閱讀 2070·2021-11-24 10:33
閱讀 2768·2021-09-23 11:33
閱讀 2562·2021-09-23 11:31
閱讀 2951·2021-09-08 09:45
閱讀 2365·2021-09-06 15:02
閱讀 2674·2019-08-30 14:21
閱讀 2341·2019-08-30 12:56
