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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/72628.html
摘要:題目鏈接題目分析給定一個(gè)單詞數(shù)組和一個(gè)字符串,判斷給定的數(shù)組是否滿足給定字符串的順序。思路按給定字符串,替換成正常順序的單詞。再判斷之前和之后的數(shù)組是否相同。最終代碼若覺(jué)得本文章對(duì)你有用,歡迎用愛(ài)發(fā)電資助。 D61 953. Verifying an Alien Dictionary 題目鏈接 953. Verifying an Alien Dictionary 題目分析 給定一個(gè)單詞...
摘要:拓?fù)渑判驈?fù)雜度時(shí)間空間思路首先簡(jiǎn)單介紹一下拓?fù)渑判颍@是一個(gè)能夠找出有向無(wú)環(huán)圖順序的一個(gè)方法假設(shè)我們有條邊,先將每個(gè)節(jié)點(diǎn)的計(jì)數(shù)器初始化為。最后,我們開(kāi)始拓?fù)渑判颍瑥挠?jì)數(shù)器為的字母開(kāi)始廣度優(yōu)先搜索。 Alien Dictionary There is a new alien language which uses the latin alphabet. However, the ord...
摘要:題目鏈接圖用,和題類似。要找到所有字母的,之后用存下入度為的字母,然后輸出。要記錄下每個(gè)字母對(duì)應(yīng)的所有字母,防止重復(fù)。求的過(guò)程可以用,從所有單詞的開(kāi)始,對(duì)不同的字母存入度,相同的去下一層。 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...
閱讀 1444·2023-04-25 16:31
閱讀 2046·2021-11-24 10:33
閱讀 2751·2021-09-23 11:33
閱讀 2537·2021-09-23 11:31
閱讀 2915·2021-09-08 09:45
閱讀 2345·2021-09-06 15:02
閱讀 2652·2019-08-30 14:21
閱讀 2321·2019-08-30 12:56