LeetCode #953 Verifying an Alien Dictionary 驗(yàn)證外星語詞典

953 Verifying an Alien Dictionary 驗(yàn)證外星語詞典

Description:
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:

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.

題目描述:
某種外星語也使用英文小寫字母钞馁,但可能順序 order 不同僧凰。字母表的順序(order)是一些小寫字母的排列熟丸。

給定一組用外星語書寫的單詞 words光羞,以及其字母表的順序 order,只有當(dāng)給定的單詞在這種外星語中按字典序排列時(shí)全闷,返回 true萍启;否則,返回 false勘纯。

示例 :

示例 1:

輸入:words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
輸出:true
解釋:在該語言的字母表中驳遵,'h' 位于 'l' 之前,所以單詞序列是按字典序排列的堤结。

示例 2:

輸入:words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
輸出:false
解釋:在該語言的字母表中,'d' 位于 'l' 之后唐责,那么 words[0] > words[1]鼠哥,因此單詞序列不是按字典序排列的。

示例 3:

輸入:words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
輸出:false
解釋:當(dāng)前三個(gè)字符 "app" 匹配時(shí)抄罕,第二個(gè)字符串相對(duì)短一些呆贿,然后根據(jù)詞典編纂規(guī)則 "apple" > "app"恍飘,因?yàn)?'l' > '?',其中 '?' 是空白字符,定義為比任何其他字符都恤婕簟(更多信息)前弯。

提示:

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
在 words[i] 和 order 中的所有字符都是英文小寫字母。

思路:

  1. 改寫比較器的方法, 按照 order的順序比較兩個(gè)字符串的長度和對(duì)應(yīng)位置的大小
  2. 按照 order的順序重新給 words中的單詞賦值, 再比較兩個(gè)字符串的大小
    時(shí)間復(fù)雜度O(mn), 空間復(fù)雜度O(1), 其中 n為 words數(shù)組的大小, m為數(shù)組中的每一個(gè)字符串的長度

代碼:
C++:

class Solution 
{
public:
    bool isAlienSorted(vector<string>& words, string order) 
    {
        int index[128] = {0};
        for (int i = 0; i < 26; i++) index[order[i]] = i + 'a';
        for (int i = 0; i < words.size(); i++) for (int j = 0; j < words[i].size(); j++) words[i][j] = index[words[i][j]];
        for (int i = 1; i < words.size(); i++) if (words[i - 1] > words[i]) return false;
        return true;
    }
};

Java:

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        Comparator<String> comparator = (a, b) -> {
            for (int i = 0; i < Math.min(a.length(), b.length()); i++) if (a.charAt(i) != b.charAt(i)) return order.indexOf(a.charAt(i)) - order.indexOf(b.charAt(i));
            return a.length() - b.length();
        };
        for (int i = 1; i < words.length; i++) if (comparator.compare(words[i - 1], words[i]) > 0) return false;
        return true;
    }
}

Python:

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        return words == sorted(words, key=lambda word: [order.index(x) for x in word]) 
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末浙巫,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子渊抄,更是在濱河造成了極大的恐慌护桦,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,946評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件贪染,死亡現(xiàn)場離奇詭異催享,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)寺渗,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門信殊,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人汁果,你說我怎么就攤上這事涡拘■Γ” “怎么了?”我有些...
    開封第一講書人閱讀 169,716評(píng)論 0 364
  • 文/不壞的土叔 我叫張陵棘利,是天一觀的道長橱野。 經(jīng)常有香客問我,道長善玫,這世上最難降的妖魔是什么水援? 我笑而不...
    開封第一講書人閱讀 60,222評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮茅郎,結(jié)果婚禮上蜗元,老公的妹妹穿的比我還像新娘。我一直安慰自己系冗,他們只是感情好奕扣,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,223評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著掌敬,像睡著了一般惯豆。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上涝开,一...
    開封第一講書人閱讀 52,807評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音瘪匿,去河邊找鬼核偿。 笑死漾岳,一個(gè)胖子當(dāng)著我的面吹牛唧垦,可吹牛的內(nèi)容都是我干的巧还。 我是一名探鬼主播,決...
    沈念sama閱讀 41,235評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼乖酬!你這毒婦竟也來了算撮?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,189評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎仰剿,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體部凑,經(jīng)...
    沈念sama閱讀 46,712評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡辉词,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,775評(píng)論 3 343
  • 正文 我和宋清朗相戀三年幢哨,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了捞镰。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片践樱。...
    茶點(diǎn)故事閱讀 40,926評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡瞭稼,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出悔雹,到底是詐尸還是另有隱情,我是刑警寧澤初肉,帶...
    沈念sama閱讀 36,580評(píng)論 5 351
  • 正文 年R本政府宣布妄壶,位于F島的核電站,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏屑埋。R本人自食惡果不足惜痰滋,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,259評(píng)論 3 336
  • 文/蒙蒙 一敲街、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧,春花似錦、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽希太。三九已至芥映,卻和暖如春坞嘀,著一層夾襖步出監(jiān)牢的瞬間裁蚁,已是汗流浹背室谚。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評(píng)論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,368評(píng)論 3 379
  • 正文 我出身青樓饰抒,卻偏偏與公主長得像枣宫,于是被迫代替她去往敵國和親翅娶。 傳聞我的和親對(duì)象是個(gè)殘疾皇子输吏,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,930評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi閱讀 7,352評(píng)論 0 10
  • **2014真題Directions:Read the following text. Choose the be...
    又是夜半驚坐起閱讀 9,592評(píng)論 0 23
  • Lua 5.1 參考手冊(cè) by Roberto Ierusalimschy, Luiz Henrique de F...
    蘇黎九歌閱讀 13,836評(píng)論 0 38
  • 萆荔穀閱讀 164評(píng)論 0 0
  • 今天的活動(dòng)取消了典唇,所以臨時(shí)決定去房山看看房子介衔,順便放放松赃泡。他爹也提前借好了車,開車去就不會(huì)覺得那么辛苦了粹胯,可其實(shí)還...
    百味雜陳閱讀 64評(píng)論 0 0