[LeetCode] 953. Verifying an Alien Dictionary

ghnor 發布于2019-08-16 13:57 / 1967人閱讀

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.

Solution

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;
    }
}

GPU云服務器云服務器 Verifying Dictionary Alien ubuntu alien

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72628.html

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
[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
Alien Dictionary

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

gaomysion 2019-08-14 17:18 評論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
[LeetCode] Longest Word in Dictionary

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...

econi 2019-08-19 11:06 評論0 收藏0