Re: [閒聊] 每日LeetCode已回收
953. Verifying an Alien Dictionary
某個外星語的單字是由小寫字母組成但是字母的順序不同，給定一個字串陣列words[]
，和一個order表示外星語的字母順序，判斷words裡面的單字是否是按照外星語的字
母順序排列，若是則返回true，否則返回false。
Example：
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: h的順序在l之前所以words[0]比words[1]小
Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: d的順序在l之後，所以words[0]比words[1]大，順序和order不同。
思路：
1.用一個map紀錄每個字的順序。
2.將字串兩兩依照map比較，如果發現前面的比後面大就返回false。
3.如果檢查完所有都合法則返回true。
Java：
--------------------------------
class Solution {
private final int[] map = new int[26];
public boolean isAlienSorted(String[] words, String order) {
for (int i = 0; i < order.length(); i++) {
map[order.charAt(i) - 'a'] = i;
}
for (int i = 1; i < words.length; i++) {
if (compare(words[i - 1], words[i]) > 0) {
return false;
}
}
return true;
}
private int compare(String s1, String s2) {
int n = Math.min(s1.length(), s2.length());
for (int i = 0; i < n; i++) {
if (map[s1.charAt(i) - 'a'] != map[s2.charAt(i) - 'a']) {
return map[s1.charAt(i) - 'a'] - map[s2.charAt(i) - 'a'];
}
}
return s1.length() - s2.length();
}
}
--------------------------------
--
https://i.imgur.com/sjdGOE3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.92.2 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1675318743.A.139.html
推
02/02 14:27,
2年前
, 1F
02/02 14:27, 1F
→
02/02 14:29,
2年前
, 2F
02/02 14:29, 2F
推
02/02 17:57,
2年前
, 3F
02/02 17:57, 3F
討論串 (同標題文章)
完整討論串 (本文為第 214 之 719 篇)：