算法题 验证外星语词典

953. 验证外星语词典

问题描述

在某种外星语言中，字母表的顺序与英语不同。给定一个字符串数组words和一个表示外星字母表顺序的字符串order，验证这些单词是否按照外星字母表的字典序排列。

字典序规则：

• 比较两个单词时，从左到右逐字符比较
• 第一个不同的字符决定两个单词的顺序
• 如果一个单词是另一个单词的前缀，则较短的单词排在前面

示例：

输入: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" 输出: true 解释: 'h' 在外星字母表中排在 'l' 前面，所以 "hello" < "leetcode" 输入: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz" 输出: false 解释: "word" 和 "world" 的前缀相同，但 "word" 是 "world" 的前缀，应该排在前面。 但 "row" 应该排在 "world" 前面，因为 'r' < 'w'，但实际上 "world" 排在 "row" 前面。 输入: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz" 输出: false 解释: "app" 是 "apple" 的前缀，应该排在前面，但实际顺序相反。

算法思路

自定义比较函数：

核心思想：

1. 建立字符映射：将外星字母表中的每个字符映射到其在字母表中的位置（0-25）
2. 逐对比较：遍历相邻的单词对，验证是否按外星字典序排列
3. 自定义比较：实现一个函数来比较两个单词在外星字母表下的字典序

比较两个单词的规则：

• 从左到右逐字符比较
• 找到第一个不同的字符，根据外星字母表顺序判断
• 如果所有对应字符都相同，较短的单词应该排在前面

代码实现

方法一：映射 + 逐对比较

classSolution{/** * 验证外星语词典是否按字典序排列 * * @param words 单词数组 * @param order 外星字母表顺序 * @return 如果单词按外星字典序排列返回true，否则返回false */publicbooleanisAlienSorted(String[]words,Stringorder){// 边界情况处理if(words==null||words.length<=1){returntrue;}// 建立字符到位置的映射int[]charOrder=newint[26];for(inti=0;i<order.length();i++){charOrder[order.charAt(i)-'a']=i;}// 验证相邻单词for(inti=0;i<words.length-1;i++){if(!isLessOrEqual(words[i],words[i+1],charOrder)){returnfalse;}}returntrue;}/** * 比较两个单词是否满足 word1 <= word2（按外星字典序） */privatebooleanisLessOrEqual(Stringword1,Stringword2,int[]charOrder){intlen1=word1.length();intlen2=word2.length();intminLength=Math.min(len1,len2);// 字符比较for(inti=0;i<minLength;i++){charc1=word1.charAt(i);charc2=word2.charAt(i);if(c1!=c2){// 找到第一个不同的字符，比较它们的外星顺序returncharOrder[c1-'a']<charOrder[c2-'a'];}}// 所有对应字符都相同，较短的单词应该排在前面returnlen1<=len2;}}

算法分析

• 时间复杂度：O©
  • C 是所有单词的字符总数
  • 需要遍历每个字符最多一次
• 空间复杂度：O(1)
  • 只需要固定大小的映射数组（26个字符）

算法过程

输入：words = ["hello","leetcode"],order = "hlabcdefgijkmnopqrstuvwxyz"

1. 建立映射：
   • 'h' → 0,'l' → 1,'a' → 2,'b' → 3, …
2. 比较 “hello” 和 “leetcode”：
   • 第一个字符：'h'vs'l'
   • 外星顺序：0 < 1
   • 返回true

输入：words = ["apple","app"],order = "abcdefghijklmnopqrstuvwxyz"

1. 比较 “apple” 和 “app”：
   • 前3个字符相同：'a','p','p'
   • “apple” 长度为5，“app” 长度为3
   • 由于没有找到不同字符且5 > 3，返回false

输入：words = ["word","world","row"],order = "worldabcefghijkmnpqstuvxyz"

1. 建立映射：'w'→0, 'o'→1, 'r'→2, 'l'→3, 'd'→4, ...
2. 比较 “word” 和 “world”：
   • 前4个字符相同
   • “word” 长度4 < “world” 长度5
3. 比较 “world” 和 “row”：
   • 第一个字符：'w'vs'r'
   • 外星顺序：0 > 2
   • 返回false

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例String[]words1={"hello","leetcode"};Stringorder1="hlabcdefgijkmnopqrstuvwxyz";System.out.println("Test 1: "+solution.isAlienSorted(words1,order1));// true// 测试用例2：前缀问题String[]words2={"apple","app"};Stringorder2="abcdefghijklmnopqrstuvwxyz";System.out.println("Test 2: "+solution.isAlienSorted(words2,order2));// false// 测试用例3：复杂无效序列String[]words3={"word","world","row"};Stringorder3="worldabcefghijkmnpqstuvxyz";System.out.println("Test 3: "+solution.isAlienSorted(words3,order3));// false// 测试用例4：单单词String[]words4={"hello"};System.out.println("Test 4: "+solution.isAlienSorted(words4,order1));// true// 测试用例5：空数组String[]words5={};System.out.println("Test 5: "+solution.isAlienSorted(words5,order1));// true// 测试用例6：两个相同单词String[]words6={"hello","hello"};System.out.println("Test 6: "+solution.isAlienSorted(words6,order1));// true// 测试用例7：正确前缀顺序String[]words7={"app","apple"};System.out.println("Test 7: "+solution.isAlienSorted(words7,order2));// true// 测试用例8：全相同首字母String[]words8={"aa","ab","ac"};Stringorder8="abcdefghijklmnopqrstuvwxyz";System.out.println("Test 8: "+solution.isAlienSorted(words8,order8));// true// 测试用例9：逆序String[]words9={"ac","ab","aa"};System.out.println("Test 9: "+solution.isAlienSorted(words9,order8));// false// 测试用例10：外星字母表完整String[]words10={"kuvp","q"};Stringorder10="ngxlkthsjuoqcpavbfdermiywz";System.out.println("Test 10: "+solution.isAlienSorted(words10,order10));// true// 'k' 在字母表中位置比 'q' 靠前// 测试用例11：长单词String[]words11={"fxasxpc","dfbdrifhp","nwzgs","cmwvwngxry","bj","nwzgs","dfbdrifhp","fxasxpc"};Stringorder11="qwertyuiopasdfghjklzxcvbnm";System.out.println("Test 11: "+solution.isAlienSorted(words11,order11));// false}

关键点

1. 字符映射：

   • 将外星字母表转换为数字索引
   • O(1) 时间复杂度的字符比较

2. 相邻对验证：

   • 字典序具有传递性
   • 只需验证相邻对就能保证全局有序

3. 前缀处理：

   • 当一个单词是另一个的前缀时，较短的应该排在前面

4. 边界情况：

   • 空数组和单元素数组
   • 相同单词的处理
   • 不同长度单词的比较

常见问题

1. 为什么只需要比较相邻单词？
   • 字典序是传递的：如果 A ≤ B 且 B ≤ C，则 A ≤ C