递归、迭代：求解《953. 验证外星语词典》
2022-05-17 12:08:12
递归、迭代两种方式，求解《953. 验证外星语词典》
Python · 初始化数组
h = [0] * 26例题
953. 验证外星语词典
某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。
答案
递归
var isAlienSorted = function(words, order) {
const h = new Uint8Array(26)
for (let i = 0; i < order.length; i++) {
h[order.charCodeAt(i) - 97] = i
}
const compare = (a, b, i) => {
if (i === a.length || i === b.length) return a.length <= b.length
const x = h[a.charCodeAt(i) - 97], y = h[b.charCodeAt(i) - 97]
return x === y ? compare(a, b, i + 1) : x < y
}
for (let i = 1; i < words.length; i++) {
if (compare(words[i - 1], words[i], 0) === false) return false
}
return true
};function isAlienSorted(words: string[], order: string): boolean {
const h = new Uint8Array(26)
for (let i = 0; i < 26; i++) h[order.charCodeAt(i) - 97] = i
const compare = (a: string, b: string, i: number): boolean => {
if (i === a.length || i === b.length) return a.length <= b.length
const x = h[a.charCodeAt(i) - 97], y = h[b.charCodeAt(i) - 97]
return x === y ? compare(a, b, i + 1) : x < y
}
for (let i = 1; i < words.length; i++) {
if (compare(words[i - 1], words[i], 0) === false) return false
}
return true
};func isAlienSorted(words []string, order string) bool {
h := [26]int{}
for i, charCode := range order {
h[charCode - 97] = i
}
var compare func(a string, b string, i int) bool
compare = func(a string, b string, i int) bool {
if i == len(a) || i == len(b) {
return len(a) <= len(b)
}
x, y := h[a[i] - 97], h[b[i] - 97]
if x == y {
return compare(a, b, i + 1)
} else {
return x < y
}
}
for i, n := 1, len(words); i < n; i++ {
if compare(words[i - 1], words[i], 0) == false {
return false
}
}
return true
}class Solution {
private $h = [];
function isAlienSorted($words, $order) {
for ($i = 0; $i < 26; $i++) {
$this->h[ord($order[$i]) - 97] = $i;
}
for ($i = 1; $i < count($words); $i++) {
if ($this->compare($words[$i - 1], $words[$i], 0) === false) return false;
}
return true;
}
function compare(&$a, &$b, $i) {
if ($i === strlen($a) || $i === strlen($b)) return strlen($a) <= strlen($b);
$x = $this->h[ord($a[$i]) - 97];
$y = $this->h[ord($b[$i]) - 97];
return $x === $y ? $this->compare($a, $b, $i + 1) : $x < $y;
}
}class Solution {
private int[] h = new int[26];
public boolean isAlienSorted(String[] words, String order) {
for (int i = 0; i < 26; i++) h[order.charAt(i) - 97] = i;
for (int i = 1; i < words.length; i++) {
if (compare(words[i - 1], words[i], 0) == false) return false;
}
return true;
}
public boolean compare(String a, String b, Integer i) {
if (i == a.length() || i == b.length()) return a.length() <= b.length();
int x = h[a.charAt(i) - 97];
int y = h[b.charAt(i) - 97];
return x == y ? compare(a, b, i + 1) : x < y;
}
}class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
h = [0] * 26
for i, char in enumerate(order):
h[ord(char) - 97] = i
def compare(a: str, b: str, i: int) -> bool:
if i == len(a) or i == len(b): return len(a) <= len(b)
x, y = h[ord(a[i]) - 97], h[ord(b[i]) - 97]
return compare(a, b, i + 1) if x == y else x < y
for i in range(1, len(words)):
if not compare(words[i - 1], words[i], 0): return False
return True迭代
var isAlienSorted = function(words, order) {
const h = new Uint8Array(26)
for (let i = 0; i < 26; i++) {
h[order.charCodeAt(i) - 97] = i
}
const compare = (a, b) => {
for (let i = 0; i < Math.min(a.length, b.length); i++) {
const x = h[a.charCodeAt(i) - 97], y = h[b.charCodeAt(i) - 97]
if (x !== y) return x < y
}
return a.length <= b.length
}
for (let i = 1; i < words.length; i++) {
if (compare(words[i - 1], words[i]) === false) return false
}
return true
};function isAlienSorted(words: string[], order: string): boolean {
const h = new Uint8Array(26)
for (let i = 0; i < 26; i++) h[order.charCodeAt(i) - 97] = i
const compare = (a: string, b: string): boolean => {
for (let i = 0; i < Math.min(a.length, b.length); i++) {
const x = h[a.charCodeAt(i) - 97], y = h[b.charCodeAt(i) - 97]
if (x !== y) return x < y
}
return a.length <= b.length
}
for (let i = 1; i < words.length; i++) {
if (compare(words[i - 1], words[i]) === false) return false
}
return true
};func isAlienSorted(words []string, order string) bool {
h := [26]int{}
for i, charCode := range order {
h[charCode - 97] = i
}
compare := func(a string, b string) bool {
for i := 0; i < len(a) && i < len(b); i++ {
x, y := h[a[i] - 97], h[b[i] - 97]
if x != y {
return x < y
}
}
return len(a) <= len(b)
}
for i, n := 1, len(words); i < n; i++ {
if compare(words[i - 1], words[i]) == false {
return false
}
}
return true
}class Solution {
private $h = [];
function isAlienSorted($words, $order) {
for ($i = 0; $i < 26; $i++) {
$this->h[ord($order[$i]) - 97] = $i;
}
for ($i = 1; $i < count($words); $i++) {
if ($this->compare($words[$i - 1], $words[$i]) === false) return false;
}
return true;
}
function compare(&$a, &$b) {
for ($i = 0; $i < min(strlen($a), strlen($b)); $i++) {
$x = $this->h[ord($a[$i]) - 97];
$y = $this->h[ord($b[$i]) - 97];
if ($x !== $y) return $x < $y;
}
return strlen($a) <= strlen($b);
}
}class Solution {
private int[] h = new int[26];
public boolean isAlienSorted(String[] words, String order) {
for (int i = 0; i < 26; i++) h[order.charAt(i) - 97] = i;
for (int i = 1; i < words.length; i++) {
if (compare(words[i - 1], words[i]) == false) return false;
}
return true;
}
public boolean compare(String a, String b) {
for (int i = 0; i < Math.min(a.length(), b.length()); i++) {
int x = h[a.charAt(i) - 97];
int y = h[b.charAt(i) - 97];
if (x != y) return x < y;
}
return a.length() <= b.length();
}
}class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
h = [0] * 26
for i, char in enumerate(order):
h[ord(char) - 97] = i
def compare(a: str, b: str) -> bool:
for i in range(min(len(a), len(b))):
x, y = h[ord(a[i]) - 97], h[ord(b[i]) - 97]
if x != y: return x < y
return len(a) <= len(b)
for i in range(1, len(words)):
if not compare(words[i - 1], words[i]): return False
return True