[LeetCode] 953. Verifying an Alien Dictionary

ghnor 发布于2019-08-16 13:57 / 1966人阅读

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

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

转载请注明本文地址：https://www.ucloud.cn/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