难度: 简单 | 标签: 字符串比较

1. 题目描述

https://leetcode.cn/problems/verifying-an-alien-dictionary/
某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 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
解释：当前三个字符 “app” 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 “apple” > “app”，因为 ‘l’ > ‘∅’，其中 ‘∅’ 是空白字符，定义为比任何其他字符都小（更多信息）。

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

通过次数: 21,259 | 提交次数: 38,170

2. 题解

2022-05-17 AC, 果然是外星语, 单词都这么恶心人

  1. <?php
  2. /**
  3.  * Created by PhpStorm
  4.  * User: jtahstu
  5.  * Time: 2022/5/17 0:31
  6.  * Des: 953. 验证外星语词典
  7.  *      https://leetcode.cn/problems/verifying-an-alien-dictionary/
  8.  */
  10. class Solution
  11. {
  13.     /**
  14.      * @param String[] $words
  15.      * @param String $order
  16.      * @return Boolean
  17.      */
  18.     function isAlienSorted($words, $order)
  19.     {
  20.         if (count($words) == 1) return true;
  21.         $order_list = [];
  22.         $len = strlen($order);
  23.         for ($i = 0; $i < $len; $i++) {
  24.             $order_list[$order[$i]] = $i;
  25.         }
  26.         for ($i = 1; $i < count($words); $i++) {
  27. //            var_dump([$words[$i], $words[$i - 1], $this->isLess($words[$i], $words[$i - 1], $order_list)]);
  28.             if (!$this->isLess($words[$i - 1], $words[$i], $order_list)) {
  29.                 return false;
  30.             }
  31.         }
  32.         return true;
  33.     }
  35.     function isLess($a, $b, &$order_list)
  36.     {
  37.         for ($i = 0; $i < strlen($a); $i++) {
  38.             if ($a[$i] == $b[$i]) continue;
  39.             if (!isset($b[$i])) return false;
  40.             if ($order_list[$a[$i]] > $order_list[$b[$i]]) return false;
  41.             else return true;
  42.         }
  43.         return true;
  44.     }
  45. }
  47. var_dump((new Solution)->isAlienSorted(["hello", "leetcode"], "hlabcdefgijkmnopqrstuvwxyz"));  //1
  48. var_dump((new Solution)->isAlienSorted(["word", "world", "row"], "worldabcefghijkmnpqstuvxyz"));  //0
  49. var_dump((new Solution)->isAlienSorted(["apple", "app"], "abcdefghijklmnopqrstuvwxyz"));  //0
  50. var_dump((new Solution)->isAlienSorted(["my", "f"], "gelyriwxzdupkjctbfnqmsavho"));  //0
  51. var_dump((new Solution)->isAlienSorted(["hello", "hello"], "abcdefghijklmnopqrstuvwxyz"));  //1
  53. /**
  54.  * 执行用时：4 ms, 在所有 PHP 提交中击败了75.00%的用户
  55.  * 内存消耗：19.2 MB, 在所有 PHP 提交中击败了25.00%的用户
  56.  * 通过测试用例：120 / 120
  57.  */